Chromatic discrepancy of locally $s$-colourable graphs

Abstract

The chromatic discrepancy of a graph $G$, denoted $\varphi (G)$, is the least over all proper colourings $\sigma$ of $G$ of the greatest difference between the number of colours $|\sigma (V(H))|$ spanned by an induced subgraph $H$ of $G$ and its chromatic number $\chi (H)$. We prove that the chromatic discrepancy of a triangle-free graph $G$ is at least $\chi (G)-2$. This is best possible and positively answers a question raised by Aravind, Kalyanasundaram, Sandeep, and Sivadasan. More generally, we say that a graph $G$ is locally $s$-colourable if the closed neighbourhood of any vertex $v\in V(G)$ is properly $s$-colourable; in particular, a triangle-free graph is locally $2$-colourable. We conjecture that every locally $s$-colourable graph $G$ satisfies $\varphi (G)\ge \chi (G)-s$, and show that this would be almost best possible. We prove the conjecture when $\chi (G)\le 11s/6$, and as a partial result towards the general case, we prove that every locally $s$-colourable graph $G$ satisfies $\varphi (G)\ge \chi (G)-s\ln \chi (G)$. If the conjecture holds, it implies in particular, for every integer $\ell \ge 2$, that any graph $G$ without any copy of $C_{\ell +1}$, the cycle of length $\ell +1$, satisfies $\varphi (G)\ge \chi (G)-\ell$. When $\ell \ge 3$ and $G\ne K_{\ell }$, we conjecture that we actually have $\varphi (G)\ge \chi (G)-\ell +1$, and prove it in the special case $\ell =3$ or $\chi (G)\le 5\ell /3$. In general, we further obtain that every $C_{\ell +1}$-free graph $G$ satisfies $\varphi (G)\ge \chi (G)-O_{\ell }(\ln \ln \chi (G))$. We do so by determining an almost tight bound on the chromatic number of balls of radius at most $\ell /2$ in $G$, which could be of independent interest.