Petersen and dodecahedral countability in C₄-free
Open Problem 2.17 · arXiv:2106.03261
Status open high confidence
The question of whether the dodecahedral and Petersen graphs (both 3-regular, girth 5) are countable in $C_4$-free graphs remains open. The source paper by Conlon, Fox, Sudakov, and Zhao (published in Pure and Applied Mathematics Quarterly 18 (2022), 2413--2432) explicitly poses this as a central open problem, noting that their 'islands and bridges' recursive construction appears insufficient for 3-regular graphs of girth at least 5. No follow-up paper resolving the problem in either direction was found across five targeted web searches.
Reviewer notes. No follow-up found after five web calls. The conjecture is ~5 years old (paper appeared in Pure and Applied Mathematics Quarterly in 2022); the absence of any hit across author pages, arXiv, and general keyword searches is strong evidence the problem remains open. The paper notes that countability requires girth at least 5 and that any d-regular countable graph must satisfy d <= 3, so the Petersen and dodecahedral graphs are the simplest cubic cases.
Context
After constructing many countable graphs of girth at least 5 via a recursive 'islands and bridges' method, the authors observe that their techniques appear insufficient to handle 3-regular graphs of girth at least 5. The dodecahedral graph (girth 5, 3-regular) and the Petersen graph (girth 5, 3-regular) are highlighted as the simplest open cases.
Notes. PDF source — figures of the two graphs referenced in the problem statement are not recoverable from the text extraction.
Source paper
Which graphs can be counted in $C_4$-free graphs?
David Conlon, Jacob Fox, Benny Sudakov, Yufei Zhao · 2021-06-06
https://arxiv.org/abs/2106.03261
PDF source