Journal of Combinatorics

Volume 8 (2017)

Number 1

Incidence coloring of planar graphs without adjacent small cycles

Pages: 167 – 187



Hervé Hocquard (LaBRI, Université de Bordeaux, Talence, France)

Samia Kerdjoudj (L’IFORCE, Faculty of Mathematics, USTHB, Algiers, Algeria)

André Raspaud (LaBRI, Université de Bordeaux, Talence, France)


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