Pendant edges suffice for k-critical bonbons
Conjecture 5.4 · arXiv:2207.07775
Status open medium confidence
No post-2023 paper was found that resolves Conjecture 5.4. The source paper itself proves the weaker Theorem 1.2 (pendant count $t$ exponentially large in $k$ suffices), and the conjecture asks whether any sufficiently large $t$ always works for any $k$-critical base graph. A related 2023 paper (arXiv:2309.06959) extends the Turán-coloring extremality framework to the off-diagonal setting for the same class of graphs, but does not address the threshold question on $t$. The conjecture remains open.
Reviewer notes. Web search (3 queries, 3 WebFetch calls) found no paper proving or disproving Conjecture 5.4. The paper arXiv:2309.06959 ('Turán Colourings in Off-Diagonal Ramsey Multiplicity') extends related results to the off-diagonal setting for graphs with pendant edges added to non-3-colorable graphs, but its abstract does not mention the threshold on t that is the subject of Conjecture 5.4. Confidence is medium rather than high because the conjecture is now roughly 3 years old and a resolution could have appeared without being prominently indexed.
Context
Theorem 1.2 proves that adding $t\geq(1000kh)^{10}h^{10k}$ pendant edges to a $k$-critical graph $H_0$ with $h$ vertices yields a bonbon, but the proof requires $t$ at least exponentially large in $k$. Moreover, if $H_0=K_k$ then some lower bound on $t$ is necessary since adding $o(k^2/\log k)$ pendant edges to $K_k$ does not produce a bonbon. The conjecture proposes that sufficiently many pendant edges always suffice for any $k$-critical base graph.
Also stated in
- Ramsey multiplicity and the Turán coloring (2023-06-27)
Source paper
Ramsey multiplicity and the Turán coloring
Jacob Fox, Yuval Wigderson · 2023-06-27
https://arxiv.org/abs/2207.07775