id: 06086242
dt: a
an: 06086242
au: Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard
ti: Coloring graphs characterized by a forbidden subgraph.
so: Rovan, Branislav (ed.) et al., Mathematical foundations of computer science
    2012. 37th international symposium, MFCS 2012, Bratislava, Slovakia,
    August 27‒31, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-32588-5/pbk). Lecture Notes in Computer Science 7464, 443-454
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-32589-2_40
ab: Summary: 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 five, or contains a connected component
    with two vertices of degree four. We also give three conditions on a
    forest $H$ of maximum degree at most four and with at most one vertex
    of degree four 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
    four.
rv: