Incidence coloring of planar graphs without adjacent small cycles

An incidence of an undirected graph $G$ is a pair $(v, e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v, e)$ and $(w, f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2012, Yang proved that every planar graph has an incidence coloring with at most $\Delta + 5$ colors, where $\Delta$ denotes the maximum degree of the graph. In this paper, we show that $\Delta+4$ colors suffice if the graph is planar and without a $C_3$ adjacent to a $C_4$. Moreover, we prove that every planar graph without $C_4$ and $C_5$ and maximum degree at least $5$ admits an incidence coloring with at most $\Delta + 3$ colors.

Full Text (PDF format)

Published 2 December 2016