Abstract
For graphs G and H, an Hcoloring of G is an edgepreserving mapping from V(G) to V(H). In the HColoring problem the graph H is fixed and we ask whether an instance graph G admits an Hcoloring. A generalization of this problem is HColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an Hcoloring.
We study the complexity of variants of HColoring in Ffree graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the kcycle by adding a universal vertex.
As our main algorithmic result we show that W_5ColoringExt is polynomialtime solvable in S_{2,1,1}free graphs. This result exhibits an interesting nonmonotonicity of HColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3Coloring, i.e., classical 3coloring, is NPhard already in clawfree (i.e., S_{1,1,1}free) graphs. Our algorithm is based on two main observations:
1) W_5ColoringExt in S_{2,1,1}free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and
2) the latter problem can be solved in polynomial time in S_{2,1,1}free graphs.
We complement this algorithmic result with several negative ones. In particular, we show that W_5Coloring is NPhard in P_tfree graphs for some constant t and W_5ColoringExt is NPhard in S_{3,3,3}free graphs of bounded degree. This is again uncommon, as usually problems that are NPhard in S_{a,b,c}free graphs for some constant a,b,c are already hard in clawfree graphs
BibTeX  Entry
@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14,
author = {D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
title = {{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5Wheel and Graphs with No Long Claws}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {14:114:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17299},
URN = {urn:nbn:de:0030drops172996},
doi = {10.4230/LIPIcs.ISAAC.2022.14},
annote = {Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension}
}
Keywords: 

graph homomorphism, forbidden induced subgraphs, precoloring extension 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 