Vertex coloring (4K1, hole-twin, 5-wheel)-free graphs

There has been recently keen interest in finding polynomial-time algorithms for the VERTEX COLORING problem for graphs G that are F-free for a given set F of graphs. If L is a set of four-vertex graphs, then the complexity of VERTEX COLORING for L-free graphs is known with three exceptions: L-1 = {claw, 4K(1)}, L-2 = {claw, 4K(1), co-diamond}, and L-3 = {4K(1), C-4}. In this paper, we study a problem arising from the class L-3. A hole is an induced cycle with at least four vertices. A hole-twin is the graph obtained from a hole by adding a vertex that forms true twins with some vertex of the hole. A 5-wheel is the graph obtained from a C-5 by adding a vertex that is adjacent to all vertices of the C-5. We prove that a (4K(1), hole-twin, 5-wheel)-free graph is perfect or has bounded clique width. As consequence we obtain a polynomial time algorithm for VERTEX COLORING for (4K(1), hole-twin, 5-wheel)-free graphs. (c) 2022 Elsevier B.V. All rights reserved.