Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Éva Czabarka, Inne Singgih and László A. Székely refute part (i) of the statement of Problem 612. Theorem 6 of the arXiv preprint (its Section 3, pp. 7--8): for every r≥2r\ge2, every δ≥2r−2\delta\ge2r-2 and every positive integer pp there is a connected (2r−1)(2r-1)-colorable, hence K2rK_{2r}-free, graph Gr,δ,pG_{r,\delta,p} of minimum degree δ\delta, order n=p((2r−1)δ+2r−3)+2n=p((2r-1)\delta+2r-3)+2 and diameter

(6r−5) n(2r−1)δ+2r−3+O(1).\frac{(6r-5)\,n}{(2r-1)\delta+2r-3}+O(1).

This ratio exceeds the conjectured 2(r−1)(3r+2)(2r2−1)δ\frac{2(r-1)(3r+2)}{(2r^2-1)\delta} exactly when δ>2(r−1)(3r+2)(2r−3)\delta>2(r-1)(3r+2)(2r-3), so part (i) fails for every r≥2r\ge2 and every δ\delta in that range with (r−1)(3r+2)∣δ(r-1)(3r+2)\mid\delta. The paper leaves the window (r−1)(3r+2)≤δ≤2(r−1)(3r+2)(2r−3)(r-1)(3r+2)\le\delta\le2(r-1)(3r+2)(2r-3) of part (i) open (its p. 2) and proposes an amended conjecture, which is not the problem.

Covers. Part (i), in full: it is a conjunction over all r≥2r\ge2 and all admissible δ\delta, so a single false instance refutes it, and this page settles it negatively. Part (ii), the question for K2r+1K_{2r+1}-free graphs, is untouched by this construction and stays open on the problem page.

Acceptance. The counterexample paper is refereed: J. Combin. Theory Ser. B 151 (2021), 38--45, issued November 2021. Czabarka, Smith and Székely restate the counterexample and its open window on p. 2 of their refereed paper in J. Graph Theory 102 (2023), 262--270, and the site's own commentary records this paper as a disproof for the case of K2rK_{2r}-free graphs, that is of part (i), while the site's label stays OPEN, which the problem page reads as leaving part (ii) open. The theorem is stated from the preprint; the published article is not held, so its theorem numbering is unchecked, and the proof is not independently checked in this corpus. The source card is czabarka_2021_counterexamples_conjecture_erdos_pach_pollack_tuza, which records the preprint and the Electron. J. Combin. article that took the preprint's kk-colorable results and holds neither file.