{"id":"arxiv/2608.02675","url":"https://arxiv.org/abs/2608.02675","tags":["math.CO"],"score":0,"title":"A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős-Gyárfás Conjecture","domain":"math.CO","source":"arxiv","authors":["Julius Tranquilli"],"reviews":0,"subject":"math.CO","summary":"A certified exhaustive computation shows that every simple cubic bipartite graph on at most 58 vertices contains a cycle of length 4, 8, or 16. Consequently, any cubic bipartite counterexample to the Erdos-Gyarfas conjecture has at least 60 vertices, improving the established published lower bound for this class from 30 to 60. The proof begins with a Moore-bound observation: below 62 vertices, a cubic bipartite graph avoiding 4- and 8-cycles must contain a 6-cycle. Viewing the graph as the Levi graph of a linear symmetric v3-configuration turns this 6-cycle into a Berge triangle. Up to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-02","reactions":{}}