A Note on Coloring (4K₁, C₄, C₆)-free graphs with a C₇

2021/10/15 by Koutecký, Martin
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2110.08004

Abstract

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₁, C₄, C₆)-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₇. In this note, we give a simpler and much faster algorithm via a more restrictive graph parameter, neighborhood diversity.

Related

• The intersection of two vertex coloring problems
• Coloring even-hole-free graphs with no star cutset
• On the structure of (4K₁, C₄, P₆)-free graphs
• The class of (2P₃,C₄,C₆)-free graphs, part II: (2P₃,C₄,C₆,C₇,T₀)-free graphs
• The class of (2P₃,C₄,C₆)-free graphs, part I: (2P₃,C₄,C₆)-free graphs that contain an induced C₇ or an induced T₀