CS Paper Radar

Improved bounds for the smallest 4-chromatic graph of girth six

Glauco Rampone

cs.DM math.CO ·submitted 2026-08-24 11:14 UTC · v1
theorycode/data

Abstract

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 SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

Comment
12 pages, 1 figure. Ancillary files: independent verification scripts, SAT certificates, and a self-contained Lean 4 formal proof. Code and data: https://github.com/glaucorampone/G64, archived at doi:10.5281/zenodo.21861488

Closest papers

Nearest neighbours by meaning across the whole index.

A proof of Wang's planar $D$-coloring conjecture

cs.DM math.CO ·2026-10-23 ·Harshit Verma
theory similarity 0.68
Abstract · 22 pages, 3 figures. Ancillary files contain the certificates and verification scripts for the computer-assisted case of maximum degree 6

We prove Wang's planar $D$-coloring conjecture. A $D$-coloring of a graph is a proper edge coloring in which every subgraph isomorphic to $K_4$ minus an edge is rainbow. Wang conjectured that every planar graph of maximum degree $Δ$ has a $D$-coloring with $9$ colors if $Δ=4$, $10$ colors if $Δ=5$, and $2Δ-1$ colors if $Δ\ge6$. Hu, Kong and Wang proved the cases $Δ\le5$ and $Δ\ge33$. We prove the sharp bound $2Δ-1$ for every $Δ\ge6$, settling the remaining cases. The proof uses discharging; the case $Δ=6$ is computer-assisted.

0.10

An Improved Upper Bound for the Turán Number of the Hexagon

cs.DM math.CO ·2026-09-09 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.65
Abstract · 9 pages

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq λn^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $λ$ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq αn^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $α$ is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.

0.27

Tweaking the constant in the Linear Hadwiger Theorem

cs.DM math.CO ·2026-10-07 ·David R. Wood
theory similarity 0.65
Abstract · v1 This paper was first submitted to the arXiv shortly before the announcement of the disproof of Hadwiger's Conjecture. v2 The main constan…

Norin and Steiner recently proved the Linear Hadwiger Conjecture. That is, there is an absolute constant $C$ such that every graph $G$ satisfies $χ(G)\leqslant C\,\text{had}(G)$, where $χ(G)$ is the chromatic number and $\text{had}(G)$ is the Hadwiger number of $G$. They estimate that their proof gives a non-optimised constant $C$ of order $10^{100}$. This paper uses AI assistance to optimise their argument, and shows that every graph $G$ satisfies $χ(G)\,\leqslant\,1{,}118{,}430\,\text{had}(G)$.

0.47

Tight Asymptotic Bounds on the Size of Order Graphs

cs.DS ·2026-10-29 ·Ruben Becker, Adrián Gómez-Brandón, Gonzalo Navarro, Nicola Prezza
theoryhot direction similarity 0.64
Abstract

Order graphs were introduced by Arroyuelo et al.\ (TODS 2024) as a generalization of the ring index, to support worst-case optimal joins on relations of arity $d$ while storing few columns: the index stores one column per edge, so its size is proportional to the number of edges of an order graph. It was known that the minimum number of edges lies between $Ω(2^d\sqrt d)$ and $O(2^d d)$, and the lower bound had been claimed to be $42$ for $d=6$. We first exhibit an optimal order graph with only $40$ edges for $d=6$, and show that the proof of that lower bound holds only for unions of cycles, whereas order graphs can be smaller than the smallest set of cycles. We give a corrected statement and proof that holds for every order graph: there must be at least $\max_m\binom dm\lceil m/2\rceil$ edges. This bound is $40$ (hence tight) for $d=6$. We then settle the asymptotic question: the minimum size is $Θ(2^d\sqrt d)$. This is obtained via an explicit construction, based on symmetric chain decompositions of the Boolean lattice, with at most $(d-1)\binom{d}{\lfloor d/2\rfloor}+2^d$ edges. The upper bound is within a factor $4+O(d^{-1/2})$ of the lower bound, and both numerically and asymptotically better than trie switching. Finally, we cast the problem as a set cover with connectivity constraints, which yields an exact ILP formulation and a greedy heuristic. With them we find optimal order graphs for $d\le 6$ in the bidirectional and for $d \le 7$ in the unidirectional model, showing that our lower bounds are tight there, and improve the best known order graphs for $d=7$ and $8$.

0.34

Erdős-Gyárfás Balanced Five-Colorings

cs.DM math.CO ·2026-10-17 ·Hai Xia, Stefan Szeider
theory similarity 0.63
Abstract

A coloring of the edges of a complete graph with $r$ colors is balanced if the edges among any $r+1$ vertices use all $r$ colors. Erdős and Gyárfás (1999) conjectured that for all $r\ge3$ the complete graph $K_{r^2+1}$ has no balanced $r$-coloring. They proved the conjecture for $r=3$ and $r=4$. We prove the conjecture for $r=5$, the first new case settled in over two decades. There is no balanced $5$-coloring of $K_{26}$, and since $K_{25}$ has one, $K_{25}$ is the largest complete graph admitting a balanced $5$-coloring. We design a reduce--dispatch--enumerate workflow, where every machine step produces an artifact that can be independently checked. First, we use a machine-checked (Lean 4) proof to reduce the conjecture to a single extremal statement about the color class with the fewest edges: no graph on $26$ vertices has between $55$ and $65$ edges while every $6$ of its vertices span between $1$ and $11$ edges. We then search on the sparse class instead of its dense complement, which makes enumeration up to isomorphism feasible. With classical stability theorems for $K_6$-free graphs, we dispatch the five near-extremal edge counts analytically. For the exhaustive enumeration on the remaining six edge counts, we design efficient encodings with SAT modulo symmetries and parallel cube-and-conquer. We also certify all eleven edge counts: each of the $12{,}296$ subproblems carries a clausal refutation checked by the independent verifier drat-trim, and all $273{,}503{,}938$ symmetry-breaking clauses are also validated against the vertex permutations that justify them.

0.21

Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable

cs.DM math.CO ·2026-09-04 ·Matheus Adauto, Celina de Figueiredo, Diana Sasaki, Rafael Schneider
similarity 0.63
Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

0.20

Lower bounds for Ramsey numbers: $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$

cs.DM math.CO ·2026-10-08 ·Fritz Cremer
theory similarity 0.63
Abstract · 8 pages, 2 figures

We prove the lower bounds $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$, improving the bounds 134 and 343 listed in the April 2026 revision of Radziszowski's dynamic survey. We give explicit red/blue colorings of $K_{134}$ with no red $K_6$ or blue $K_8$, and of $K_{344}$ with no red $K_8$ or blue $K_{10}$, and verify them with two independently written exhaustive clique checkers. Starting from published colorings, we find these witnesses by adding vertices and repairing the resulting monochromatic cliques through local search. The search uses exact conflict counts, preparation moves aimed at making remaining cliques cheaper to break, and mutations followed by repair. A loss based on the largest monochromatic clique containing each edge yielded a useful intermediate state for the $\mathrm{R}(6,8)$ construction. Guided by the author, an AI coding agent wrote and ran the search code; we describe the methods and document the ancestry of the resulting colorings.

0.11

The chromatic number of the associahedron: simple and logarithmic

cs.DS math.CO ·2026-10-08 ·Benjamin Aram Berendsohn, Jean Cardinal, John Iacono, László Kozma
similarity 0.63
Abstract

Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the $n$-dimensional associahedron has chromatic number at most $22500\cdot\log_3 n+O(1)$. We present a much simpler proof that the chromatic number of the $n-1$-dimensional associahedron is at most $6 \log_2 n + 18$. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to $O(\log \log n)$ by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.

0.29