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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-02 Page: https://delphi.science/r/arxiv/2608.02675 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…