New bounds for odd colourings of graphs
Résumé
Given a graph $G$, a vertex-colouring $σ$ of $G$, and a subset $X\subseteq V(G)$, a colour $x \in σ(X)$ is said to be \emph{odd} for $X$ in $σ$ if it has an odd number of occurrences in $X$. We say that $σ$ is an \emph{odd colouring} of $G$ if it is proper and every (open) neighbourhood has an odd colour in $σ$. The odd chromatic number of a graph $G$, denoted by $χ_o(G)$, is the minimum $k\in\mathbb{N}$ such that an odd colouring $σ\colon V(G)\to [k]$ exists. In a recent paper, Caro, Petru\v sevski and \v Skrekovski conjectured that every connected graph of maximum degree $Δ\ge 3$ has odd-chromatic number at most $Δ+1$. We prove that this conjecture holds asymptotically: for every connected graph $G$ with maximum degree $Δ$, $χ_o(G)\leΔ+O(\lnΔ)$ as $Δ\to \infty$. We also prove that $χ_o(G)\le\lfloor3Δ/2\rfloor+2$ for every $Δ$. If moreover the minimum degree $δ$ of $G$ is sufficiently large, we have $χ_o(G) \le χ(G) + O(Δ\ln Δ/δ)$ and $χ_o(G) = O(χ(G)\ln Δ)$. 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.