Erdős–Lovász Tihany conjecture

Status partial high confidence

The Erdős–Lovász Tihany conjecture (Lovász 1968) remains open in full generality as of 2026. Substantial partial progress has been made: Stiebitz (1987, pre-2008) proved the case k₁=2 for all k₂; subsequent work has confirmed the conjecture for claw-free graphs (Chudnovsky–Fradkin–Plumettaz 2013), for graphs with forbidden holes (Song 2018), for line graphs of multigraphs and for graphs with independence number two (Wang–Yu 2020), and most recently for all even-hole-free graphs (Song 2026). The general statement for arbitrary k-chromatic triangle-free-in-clique graphs is still open.

Cited literature (7)

• partial On the Erdős-Lovász Tihany Conjecture for Claw-Free Graphs (2013)
  Chudnovsky, Maria; Fradkin, Alexandra; Plumettaz, Matthieu · arXiv preprint · arXiv:1309.1020

  Proves the Erdős–Lovász Tihany conjecture for the class of claw-free graphs.

• partial Erdős-Lovász Tihany Conjecture for graphs with forbidden holes (2018)
  Song, Zi-Xia · arXiv preprint · arXiv:1805.11437

  Proves the conjecture for k-chromatic graphs whose forbidden induced subgraphs include specified odd or even holes.

• partial Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs (2020)
  Wang, Yue; Yu, Gexin · arXiv preprint · arXiv:2008.08015

  Proves and strengthens the conjecture for line graphs of multigraphs.

• partial Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two (2020)
  Wang, Yue; Yu, Gexin · arXiv preprint · arXiv:2008.08017

  Proves and strengthens the conjecture for graphs with independence number at most two.

• partial Some remarks on even-hole-free graphs (2021)
  Song, Zi-Xia · arXiv preprint · arXiv:2106.01136

  Contains results on the conjecture for even-hole-free graphs (precursor to Song 2026).

• partial Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs (2024)
  Longbrake, Sean; Tariq, Juvaria · arXiv preprint · arXiv:2406.15164

  Establishes additional cases of the conjecture for claw-free graphs beyond those in Chudnovsky–Fradkin–Plumettaz (2013).

• partial The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs (2026)
  Song, Zi-Xia · arXiv preprint · arXiv:2607.20376

  Proves the full conjecture for the class of all even-hole-free graphs (graphs containing no induced cycle of even length ≥ 4).

Reviewer notes. The special case k₁=2 (any k₂≥2) is the 'double-critical graph conjecture' (OPG record double_critical_graph_conjecture, still open for χ(G)≥6) and is a strictly weaker statement. Individual arXiv abstract pages were not fetched due to the 8-call cap; all seven paper entries (titles, authors, years, arXiv IDs) were retrieved from the arXiv full-text search results page for the query 'Tihany conjecture' and should be treated as high-confidence but individually unconfirmed. The classical Stiebitz (1987, Combinatorica 7) result proving the case k₁=2 predates 2008 and is not in since_posted but is the main pre-2008 partial result. No paper claims a proof of the full conjecture; all post-2008 results are for restricted graph classes.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).