A Note on Coloring (4K(1), C-4, C-6)-Free Graphs with a C-7

Abstrakt

Even-hole-free graphs are a graph class of much interest. Foley et al. (Graphs Comb. 36(1):125-138, 2020) have recently studied (4K(1), C-4, C-6)-free graphs, which form a subclass of even-hole-free graphs.

Specifically, Foley et al. have shown an algorithm for coloring these graphs via bounded clique-width if they contain a C-7. In this note, we give a simpler and much faster algorithm via a more restrictive graph parameter, neighborhood diversity.

Klíčová slova

• Graph coloring
• Neighborhood diversity
• Integer programming