{"id":"arxiv/2608.23652","url":"https://arxiv.org/abs/2608.23652","tags":["math.CO","cs.DM"],"score":0,"title":"Improved bounds for the smallest 4-chromatic graph of girth six","domain":"math.CO","source":"arxiv","authors":["Glauco Rampone"],"reviews":0,"subject":"math.CO","summary":"For integers $k,g \\ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \\le n_6(4) \\le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \\le n_6(4) \\le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-24","reactions":{}}