Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs (Q2124227)

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\). The authors show that a (\(4K_1\), hole-twin, \(5\)-wheel)-free graph is perfect or has a bounded clique width. As a consequence they obtain a polynomial-time algorithm for the VERTEX COLORING for (\(4K_1\), hole-twin, \(5\)-wheel)-free graphs. This is another class of \(F\)-free graphs for a given set \(F\) of graphs for which there is a polynomial-time algorithm for the VERTEX COLORING problem.