{"id":"arxiv/2609.28594","url":"https://arxiv.org/abs/2609.28594","tags":["math.CO"],"score":0,"title":"Towards a more structured search for Erdős-Gyárfás counter-examples","domain":"math.CO","source":"arxiv","authors":["Guillaume Ducoffe","Bogdan Dumitru"],"reviews":0,"subject":"math.CO","summary":"The Erdős-Gyárfás conjecture posits that every graph with minimum degree at least three contains a cycle of length some power of two. We prove a few simple structural properties for any minimal counter-example to this conjecture. In particular, the fraction of its vertices of degree three must be greater than $2/3$, thus improving on the prior bound of $4/7$ (Carr, 2026). Furthermore, it is either biconnected or the $1$-clique-sum of two biconnected graphs. By exploiting some of these properties, we were able to verify the conjecture for every graph of order at most $40$, every bipartite…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}