K_l-critical graph conjecture

For an integer 2\ell\geq 2, call a graph GG KK_{\ell}-critical if it contains a copy of KK_{\ell}, is vertex-critical, and removing the vertex set of any copy of KK_{\ell} reduces its chromatic number by \ell. KK_{\ell}-critical graph conjecture. If GG is KK_{\ell}-critical for some 2\ell\geq 2, then GG is a complete graph. This conjecture generalizes the double-critical graph conjecture and is presented as an open strengthening motivated by counterexamples to the Erdős–Lovász–Tihany conjecture.

Sources & referencesView supporting material

Primary source

Sean Longbrake and Juvaria Tariq, “Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs”, arXiv:2406.15164 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.