Towards a more structured search for Erdős-Gyárfás counter-examples
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.28594
curl -X POST /api/v1/records/arxiv/2609.28594/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28594/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'