Sparse $4$-critical graphs have low circular chromatic number

Abstract

Kostochka and Yancey proved that every $4$-critical graph $G$ has $e(G)\ge \frac{5v(G)-2}{3}$, and that equality holds if and only if $G$ is $4$-Ore. We show that a question of Postle and Smith-Roberge implies that every $4$-critical graph with no $(7,2)$-circular-colouring has $e(G)\ge \frac{27v(G)-20}{15}$. We prove that every $4$-critical graph with no $(7,2)$-colouring has $e(G)\ge \frac{17v(G)}{10}$ unless $G$ is isomorphic to $K_4$ or the wheel on six vertices. We also show that if the Gallai Tree of a $4$-critical graph with no $(7,2)$-colouring has every component isomorphic to either an odd cycle, a claw, or a path. In the case that the Gallai Tree contains an odd cycle component, then $G$ is isomorphic to an odd wheel. In general, we show a $k$-critical graph with no $(2k-1,2)$-colouring that contains a clique of size $k-1$ in it's Gallai Tree is isomorphic to $K_k$.

29 pages