Towards a more structured search for Erd\H{o}s-Gy\'arf\'as counter-examples
En palabras de los autores
The Erd\H{o}s-Gy\'arf\'as 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 , thus improving on the prior bound of (Carr, 2026). Furthermore, it is either biconnected or the -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 , every bipartite graph of order at most , and every cubic graph of order at most .
Resultado principalLimitación que admiten los autores
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.