Abstract
(4K(1),C-4,C-6)-free graphs are precisely the even-hole-free graphs of stability number at most three. We show that (4K(1),C-4,C-6)-free graphs can be recognized in (n(3)) time, and furthermore, that all the following can be computed in (n(3)) time for such graphs: an optimal coloring, a minimum clique cover, and the list of all maximal cliques.
We also show that every (4K(1),C-4,C-6)-free graph on n vertices has at most n maximal cliques.@2022 Elsevier B V All rights reserved.