F-counting lemma in C₄-free graphs
Question 1.1 · arXiv:2106.03261
Status open high confidence
The central question of Conlon–Fox–Sudakov–Zhao (arXiv:2106.03261) — for which graphs $F$ is there an $F$-counting lemma in $C_4$-free graphs? — remains open as of 2026. The paper establishes that girth at least 5 is a necessary condition for countability and constructs infinite families of countable graphs (including $C_5$), but a complete characterization is not known. The status of specific 3-regular graphs of girth 5 such as the Petersen graph and the dodecahedral graph is still unresolved, as noted in subsequent survey literature (e.g., Zhao's textbook slides).
Reviewer notes. No follow-up paper resolving the full characterization was found across four targeted web searches. The paper is at v1 (no revision) as of the review date. Zhao's sparse regularity slides (yufeizhao.com) list the Petersen and dodecahedral graphs as explicit open problems, confirming the conjecture remains open. The 2-density condition ($m_2(F) < 2$) is a further necessary condition discussed informally in the paper.
Context
This is the central open problem of the paper. The authors formally define what it means for a graph $F$ to be 'countable' (Definition 1.3) and construct infinite families of countable graphs, but a complete characterization remains open. They note that a necessary condition is that $F$ has girth at least 5 (Remark 1.6).
Notes. Labeled '(Main question, informal)' in the paper; the informal qualifier refers to the prose level of precision, not the environment type.
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