Coloring even-hole-free graphs with no star cutset

2018/05/04 by Ngoc Khang Le, Le, Ngoc Khang
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1805.01948

openalex publication_date 2018/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A hole is a chordless cycle of length at least 4. A graph is even-hole-free if it does not contain any hole of even length as an induced subgraph. In this paper, we study the class of even-hole-free graphs with no star cutset. We give the optimal upper bound for its chromatic number in terms of clique number and a polynomial-time algorithm to color any graph in this class. The latter is, in fact, a direct consequence of our proof that this class has bounded rank-width.

Related

• Structure and algorithms for (cap, even hole)-free graphs
• A note on coloring (even-hole,cap)-free graphs
• Coloring graphs with no even hole ≥ 6: the triangle-free case
• On the structure of (pan, even hole)-free graphs
• A Note on Coloring (4K₁, C₄, C₆)-free graphs with a C₇