Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs

2024/06/21 by Sean Longbrake, Longbrake, Sean, Juvaria Tariq +1
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2406.15164

openalex publication_date 2024/06/21 · openalex created_date 2024/06/25 · openalex updated_date 2026/07/28

Abstract

The Erdős-Lovász Tihany Conjecture states that any G with chromatic number χ(G) = s + t - 1 > ω(G), with s,t ≥ 2 can be split into two vertex-disjoint subgraphs of chromatic number s, t respectively. We prove this conjecture for pairs (s, t) if t ≤ s + 2, whenever G has a K_s, and for pairs (s, t) if t ≤ 4 s - 3, whenever G contains a K_s and is claw-free. We also prove the Erdős Lovász Tihany Conjecture for the pair (3, 10) for claw-free graphs.

Related

• On the Erdös-Lovász Tihany Conjecture for Claw-Free Graphs
• Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two
• The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs
• Erdős-Lovász Tihany Conjecture for graphs with forbidden holes
• On the Erdős-Gyárfás conjecture in claw-free graphs