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 , every and every positive integer there is a connected -colorable, hence -free, graph of minimum degree , order and diameter
This ratio exceeds the conjectured exactly when , so part (i) fails for every and every in that range with . The paper leaves the window 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 and all admissible , so a single false instance refutes it, and this page settles it negatively. Part (ii), the question for -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 -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 -colorable results and holds neither file.