Publikace na Matematicko-fyzikální fakulta |
2022
Abstrakt
We give a complete structural description of (4K1,C4,C6,C7)-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 (4K1,C4,C6)-free graphs that do not contain a simplicial vertex have bounded clique-width.
Consequently, Graph Coloring can be solved in polynomial time for (4K1,C4,C6)-free graphs, that is, for even-hole-free graphs of stability number at most three.