On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
Irena Penev · Journal of Graph Theory · 2021
Abstract We give a complete structural description of ‐free graphs that do not contain a simplicial vertex, and we prove that such graphs have bounded clique‐width. Together with the results of Foley et al., this implies that ‐free graphs that do not contain a simplicial vertex have bounded clique‐width. Consequently, Graph Coloring can be solved in polynomial time for ‐free graphs, that is, for even‐hole‐free graphs of stability number at most three.