COMPLEXITY DICHOTOMY FOR LIST-5-COLORING WITH A FORBIDDEN INDUCED SUBGRAPH

For a positive integer r and graphs G and H, we denote by G + H the disjoint union of G and H and by r H the union of r mutually disjoint copies of H. Also, we say G is H - freeif H is not isomorphic to an induced subgraph of G. We use P t to denote the path on t vertices. For a fixed positive integer k, the LlST-fc-COLORING PROBLEM is to decide, given a graph G and a list L (v) C ( 1,..., k ) of colors assigned to each vertex v of G, whether G admits a proper coloring <j> with 4> (v) ∊ L (v) for every vertex v of G, and the fc-COLORING PROBLEM is the LlST-fc-COLORING PROBLEM restricted to instances with L (v) = (1,..., k ) for every vertex v of G. We prove that, for every positive integer r, the LlST-5-COLORING PROBLEM restricted to rP3-free graphs can be solved in polynomial time. Together with known results, this gives a complete dichotomy for the complexity of the LlST-5-COLORING PROBLEM restricted to H-free graphs: For every graph H, assuming P=NP, the LlST-5-COLORING PROBLEM restricted to H-free graphs can be solved in polynomial time if and only if, H is an induced subgraph of either r P3 or P5 + rP1 for some positive integer r. As a hardness counterpart, we also show that the fc-COLORING PROBLEM restricted to rP4-free graphs is NP-complete for all k > 5 and r > 2.