Title: 3-Colorability in P for P6-free Graphs

Authors: Bert Randerath and Ingo Schiermeyer  

Abstract:
In this paper we study an chromatic aspect for the class of P6-free graphs. Here, the focus of our interest are graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colorability can be decided in polynomial time and, if so, a proper 3-coloring can be determined also in polynomial time. Note that the 3-colorability decision problem is a well-known NP-complete problem, even for special graph classes (e.g. triangle-free and K_{1,5}-free). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-coloring of a given graph in general. Our approach is based on an encoding of the problem with boolean formulas making use of the existence of bounded dominating subgraphs. Together with a structural analysis of the non-perfect K4-free members of the graph class in consideration we obtain our main result that 3-colorability can be decided in polynomial time for the class of P6-free graphs.