4-regular 4-chromatic graphs of high girth

4-regular 4-chromatic graphs of high girth

Definitions and mathematical statement

For a finite simple graph $G$, $4$-regularity means that every vertex has exactly four distinct neighbours. A proper $q$-colouring is a function $c:V(G)\to\{1,\ldots,q\}$ assigning different values to adjacent vertices. The chromatic number $\chi(G)$ is the least number of colours permitting such a function. The girth is the length, in edges, of a shortest simple cycle.

The problem asks for the following existence statement: \[ \forall g\in\mathbb Z_{\geq3}\quad\exists G: \quad G\text{ finite simple and $4$-regular},\quad \chi(G)=4,\quad\operatorname{girth}(G)\geq g. \] The order of $G$ may depend on $g$ and is not bounded in advance. Requiring girth greater than $g$ gives the same unbounded-girth question after shifting the parameter by one.

The equality $\chi(G)=4$ requires both a proper four-colouring and the impossibility of a proper three-colouring. Degree exactly four must hold at every vertex, not just on average or as a maximum degree bound. All cycles, including odd and even ones, are excluded below the chosen girth threshold.

Connected witnesses may be requested without changing the problem: some component of a graph with chromatic number four has chromatic number four, and a component of a regular graph keeps its degrees and has no shorter cycle. Conversely, a negative answer would give one finite girth threshold beyond which no such graph exists.

Short English statement

Are there 4-regular graphs requiring exactly four colours with no cycle below any prescribed length?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Literature and scope.

The original Garden entry [S2] attributes this fixed-degree question to Grünbaum. General existence of graphs with large girth and chromatic number does not keep degree exactly four. We checked the explicit Chvátal graph data in the official NetworkX implementation [S3], then independently verified its properties below. This supplies the girth-four case and a reproducible finite certificate, not an assertion that the historical page lists all currently known examples.

An explicit graph and four-colouring.

Use vertices $0,\ldots,11$ and the following neighbour lists, recording each undirected edge only once: \[ \begin{array}{c|l} 0&1,4,6,9\\1&2,5,7\\2&3,6,8\\3&4,7,9\\ 4&5,8\\5&10,11\\6&10,11\\7&8,11\\8&10\\9&10,11 \end{array} \] There are twenty-four distinct edges, every vertex has degree four, and there are no loops. Direct triangle testing finds none, while $0,1,5,4,0$ is a four-cycle. Hence the girth is exactly four. A proper four-colouring, listed in vertex order, is \[ (0,1,0,1,2,0,1,0,1,2,3,3). \] Checking each listed edge confirms distinct endpoint colours.

An exhaustive lower-colour certificate.

For this fixed graph, the companion script scripts/check_attempt_batch02_graphs_2026_10_01.py enumerates all $\binom{12}{5}=792$ five-element sets and finds that none is independent. It separately enumerates all $\binom{12}{4}=495$ four-element sets and finds exactly twenty independent ones. Of the $\binom{20}{2}=190$ pairs of these sets, exactly sixty-four are disjoint. For each disjoint pair, the remaining four vertices contain an edge.

These finite facts imply non-three-colourability: every colour class has at most four vertices, so a three-colouring of twelve vertices would partition them into three independent four-sets. Its first two sets would be one of the sixty-four disjoint pairs, with an independent complement, which the exhaustive check excludes. Thus the displayed graph has chromatic number exactly four and proves the requested existence for every threshold $g\le4$. The script uses only the listed edge set, combination generation and edge tests; there is no graph-library chromatic-number oracle or heuristic search result in this certificate.

A necessary size bound for extending the construction.

A simple 4-regular graph of girth at least $2r+1$ has at least \[ 1+4\sum_{i=0}^{r-1}3^i \] vertices. Explore from a vertex to depth $r$. The first level has four vertices and subsequent levels have three fresh children per vertex. A repeated vertex or a non-tree edge within levels below the last would close a cycle of length at most $2r$, contradicting the girth assumption. Edges solely between last-level vertices need not be forbidden for this count. For girth at least $2r$, exploring from both ends of an edge, excluding that edge, to depth $r-1$ similarly gives at least \[ 2\sum_{i=0}^{r-1}3^i \] vertices: a collision within either tree or between the two trees would create a cycle shorter than $2r$. These lower bounds quantify why a bounded collection of small graphs cannot establish arbitrarily large girth.

Why a standard covering trick loses the target.

The bipartite double cover has vertices $(v,0),(v,1)$ and replaces $uv$ by $(u,0)(v,1)$ and $(u,1)(v,0)$. It preserves degree four, but colouring by the second coordinate gives a proper two-colouring. Thus it cannot turn this certificate into a 4-chromatic graph of larger girth. More generally, a colouring can become easier after passing to a cover; lifting edges does not preserve a chromatic lower bound. Even cycles of the base lift to cycles of the same length in this particular cover, so it does not eliminate all short cycles either.

Final status.

The girth-four existence certificate and the necessary size bounds are checked. No construction here raises the girth without losing four-chromaticity, and no finite test decides the universal quantifier over $g$. The arbitrarily-high-girth assertion is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3193 (OPG-830), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 4-regular 4-chromatic graphs of high girth. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/high_girth_low_degree_4_chromatic_graphs.
• S3 NetworkX developers, official source for chvatal_graph in networkx.generators.small, checked 1 October 2026. Used only for the explicit adjacency data; all relevant graph properties are independently checked in the accompanying script. https://networkx.org/documentation/stable/_modules/networkx/generators/small.html#chvatal_graph.