
A minimal counterexample to the Erdős–Gyárfás conjecture is a graph of minimum possible order and, subject to that, minimum possible size, with minimum degree at least 3 and containing no cycle whose length is a power of 2. Carr recently showed that at least 4/7 of the vertices of any minimal counterexample have degree exactly 3. We observe that combining two structural facts already established in that work yields the stronger bound 2/3, and we prove an additional structural restriction: whenever the four edges leaving a pair of adjacent cubic vertices all end in vertices of degree at least 4, the pair has a unique common neighbor, and that common neighbor has degree exactly 4.
Graph theory, Combinatorics, Erdős–Gyárfás conjecture, extremal graph theory, cubic graphs, minimal counterexample, cycles of power-of-two length
Graph theory, Combinatorics, Erdős–Gyárfás conjecture, extremal graph theory, cubic graphs, minimal counterexample, cycles of power-of-two length
| citations The total number of citations received by all articles of the researcher of interest. | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
