3-Colorability ∈P for P6-free graphs

✍ Scribed by Bert Randerath; Ingo Schiermeyer

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 337 KB
• Volume: 136
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00446-3

✦ Synopsis

In this paper, we study a chromatic aspect for the class of P6-free graphs. Here, the focus of our interest are graph classes (deÿned 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. for triangle-and K1;5-free graphs (Discrete Math. 162 (1-3) (1996) 313-317). 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.