Jianhua Tu

The incidence coloring conjecture, introduced in 1993 by Brualdi and Massey \cite{bru},states that the incidence coloring number of every graph is at most ${\it\Delta}+2$, where ${\it\Delta}$ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli \cite{gui} in 1997, following the work of I. Algor and N. Alon. However, in 2005, Maksim Maydanskiy \cite{may} proved that the conjecture holds for any graph with ${\it\Delta}\leq3$. In this paper, we show that it is NP-complete to determine the incidence coloring number of an arbitrary graph. The problem remains NP-complete even for semi-cubic graphs.