4-colorability of P6-free graphs

In this paper we will study the complexity of 4-colorability in subclasses of P6-free graphs. The well known k-colorability problem is NP-complete. It has been shown that if k-colorability is solvable in polynomial time for an induced H-free graph, then every component of H is a path. Recently, Huang [S. Huang, Improved Complexity Results on k-Coloring Pt-Free Graphs, Proc. MFCS, LNCS 8087 (2013) 551558] has shown several improved complexity results on k-coloring Pt-free graphs, where Pt is an induced path on t vertices. In summer 2014 only the case k=4, t=6 remained open for all k≥4 and all t≥6. Huang conjectures that 4-colorability of P6-free graphs can be decided in polynomial time. This conjecture has shown to be true for the class of (P6, banner)-free graphs by Huang [S. Huang, Improved Complexity Results on k-Coloring Pt-Free Graphs, Proc. MFCS, LNCS 8087 (2013) 551558] and for the class of (P6, C5)-free graphs by Chudnovsky et al. [M. Chudnovsky, P. Maceli, J. Stacho, and M. Zhong, 4-coloring P6-free graphs with no induced 5-cycles, submitted]. In this paper we show that the conjecture also holds for the class of (P6, bull, Z2)-free graphs, for the class of (P6, bull, kite)-free graphs, and for the class of (P6, chair)-free graphs.