The odd chromatic number of a planar graph is at most 8

Abstract

Petruševski and Škrekovski \cite{odd9} recently introduced the notion of an odd colouring of a graph: a proper vertex colouring of a graph $G$ is said to be \emph{odd} if for each non-isolated vertex $x\in V(G)$ there exists a colour $c$ appearing an odd number of times in $N(x)$. Petruševski and Škrekovski proved that for any planar graph $G$ there is an odd colouring using at most $9$ colours and, together with Caro \cite{oddremarks}, showed that $8$ colours are enough for a significant family of planar graphs. We show that $8$ colours suffice for all planar graphs.

References in corpus (1)

• Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods

Cited by in corpus (1)

• On odd colorings of sparse graphs