OpenAlex ·
Towards a more structured search for Erdős-Gyárfás counter-examples
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.28594
- Original
- Read it at the publisher
- Topics
Abstract
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 graph of order at most $66$, and every cubic graph of order at most $48$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Minimal representations of topology-preserving quantum-like states
Boolean threshold functions, neuron capacity, and memory retrieval
Sampling Line-Graph Colorings with Constant Extra Colors
Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
A 27 x 27 x 27 counterexample to Comon's conjecture
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.