Wiki
Wiki

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

Updated


Claim. Stijn Cambie and Jorik Jooken show that 33-colorable, hence K4K_4-free, connected graphs of minimum degree 1616 can have diameter at least 31216n+O(1)\frac{31}{216}n+O(1) (Table 1 and the following paragraph on p. 4, the δ=16\delta=16 block on p. 11 of the preprint; the lower bound f′(16)≥31/216f'(16)\ge31/216 is stated as unconditional, its exactness as conditional on mild assumptions). Part (i) of the statement of Problem 612 at r=2r=2, δ=16\delta=16, where 8∣168\mid16 as required, asserts D≤167n16+O(1)=n7+O(1)D\le\frac{16}{7}\frac{n}{16}+O(1)=\frac n7+O(1), and 31216>17\frac{31}{216}>\frac17. The instance lies inside the window 8≤δ≤168\le\delta\le16 that Czabarka, Singgih and Székely left open at r=2r=2; Cambie and Jooken's data (Table 1) support the conjectured ratio 2/72/7 at δ=8\delta=8, the window's other admissible value.

Covers. Part (i), in full: one false instance refutes it, so this is a second disproof of part (i), beside the refereed one of Czabarka, Singgih and Székely. It does not bear on part (ii).

Standing. A preprint (arXiv v1 of 12 February 2025, 16 pages); no later version and no journal record were found on 2026-09-17. The site's commentary cites the example as a further counterexample to the original conjecture and thanks the first author, and the page's label stays OPEN and the proof-claim tab is empty. The construction's statement is paged on the result page counterexample_p4 at claims checked; the computer search behind the δ=16\delta=16 block is the authors' own. The claim therefore stays claimed; the standing of part (i) rests on the refereed counterexamples.