Preprint
A cubic chromatic bound for capped graphs
Mathematics
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 $\chi(G)\leq\min\{3^{\omega(G)-1},18\omega(G)^3\}$, where $\chi(G)$ and $\omega(G)$ are its chromatic number and clique number. This proves a conjecture of Davies, Krawczyk, McCarty and Walczak.