New bounds for odd colourings of graphs

Abstract

Given a graph $G$, a vertex-colouring $\sigma$ of $G$, and a subset $X\subseteq V(G)$, a colour $x\in \sigma (X)$ is said to be \emph{odd} for $X$ in $\sigma$ if it has an odd number of occurrences in $X$. We say that $\sigma$ is an \emph{odd colouring} of $G$ if it is proper and every (open) neighbourhood has an odd colour in $\sigma$. The odd chromatic number of a graph $G$, denoted by ${\chi }_o(G)$, is the minimum $k\in \mathbb{N}$ such that an odd colouring $\sigma :V(G)\to [k]$ exists. In a recent paper, Caro, Petru\v sevski and \v Skrekovski conjectured that every connected graph of maximum degree $\Delta \ge 3$ has odd-chromatic number at most $\Delta +1$. We prove that this conjecture holds asymptotically: for every connected graph $G$ with maximum degree $\Delta$, ${\chi }_o(G)\le \Delta +O(\ln \Delta )$ as $\Delta \to \infty$. We also prove that ${\chi }_o(G)\le \lfloor 3\Delta /2\rfloor +2$ for every $\Delta$. If moreover the minimum degree $\delta$ of $G$ is sufficiently large, we have ${\chi }_o(G)\le \chi (G)+O(\Delta \ln \Delta /\delta )$ and ${\chi }_o(G)=O(\chi (G)\ln \Delta )$. Finally, given an integer $h\ge 1$, we study the generalisation of these results to $h$-odd colourings, where every vertex $v$ must have at least $\min \{°(v),h\}$ odd colours in its neighbourhood. Many of our results are tight up to some multiplicative constant.