2021/06/02 by Zi‐Xia Song, Song, Zi-Xia
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2106.01136
openalex publication_date 2021/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex of a graph is bisimplicial if the set of its neighbors is the union of two cliques; a graph is quasi-line if every vertex is bisimplicial. A recent result of Chudnovsky and Seymour asserts that every non-empty even-hole-free graph has a bisimplicial vertex. Both Hadwiger's conjecture and the Erdős-Lovász Tihany conjecture have been shown to be true for quasi-line graphs, but are open for even-hole-free graphs. In this note, we prove that for all k≥7, every even-hole-free graph with no Kk minor is (2k-5)-colorable; every even-hole-free graph G with ω(G) χ(G)/3. Furthermore, we prove that every 9-chromatic graph G with ω(G)≤ 8 has a K4∪ K6 minor. Our proofs rely heavily on the structural result of Chudnovsky and Seymour on even-hole-free graphs.