Golovach, Petr A. Paulusma, Daniël Ries, Bernard 2014 The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H-free and initiate a complexity classification of Coloring for strongly H-free graphs. We show that Coloring is NP-complete for strongly H-free graphs, even for k = 3, when H contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest H of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NP-complete for strongly H-free graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly H-free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most 4. application/pdf https://sonar.ch/global/documents/322636 https://sonar.ch/documents/322636/files/coloring.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2014.08.008 info:eu-repo/semantics/altIdentifier/issn/0166-218X info:eu-repo/semantics/openAccess Rights reserved Discrete Applied Mathematics. - Elsevier BV. - 2014, vol. 180, p. 101-110 Applied Mathematics Discrete Mathematics and Combinatorics Complexity Algorithms Graph coloring Forbidden subgraph info:eu-repo/classification/udc/004 Coloring graphs characterized by a forbidden subgraph http://purl.org/coar/resource_type/c_6501