Paperlane

no. 4 · Wednesday 28 October 2026

A cubic chromatic bound for capped graphs

Hongyang Wang

math.CO · 10 pp

Abstract

An ordered graph is capped if, for any four vertices $a<b<c<d$, the edges $ac$ and $bd$ imply the edge $ad$. We prove that every nonempty capped graph $G$ satisfies $χ(G)\leq\min\{3^{ω(G)-1},18ω(G)^3\}$, where $χ(G)$ and $ω(G)$ are its chromatic number and clique number. This proves a conjecture of Davies, Krawczyk, McCarty and Walczak.

comments
10 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.37578 ↗