On incidence coloring of Cartesian products of graphs

Petr Gregor, Borut Lužar

Published 2015-05-19Version 1

An incidence in a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are \textit{adjacent} if at least one of the following holds: $(i)$ $v = u$, $(ii)$ $e = f$, or $(iii)$ $vu \in \{e,f\}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $\Delta(G) + 2$ colors are needed for an incidence coloring of any graph $G$. The conjecture is false in general, but the bound holds for many classes of graphs. We prove it for a wide subclass of Cartesian products of graphs. As a corollary, we infer that it holds for hypercubes answering in affirmative a conjecture of Pai et al.~(Pai et al., Incidence coloring of hypercubes, Theor. Comput. Sci. 557 (2014), 59--65).