R. Janczewski, A. Małafiejska , M. Małafiejski
On incidence coloring of complete multipartite and semicubic bipartite graphs
Discussiones Mathematicae Graph Theory
Received 08.03.2016, Revised 07.10.2016, Accepted 14.10.2016, doi: 10.7151/dmgt.1995

In the paper, we show that the incidence chromatic number χi of a complete k-partite graph is at most Δ+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to Δ+1 if and only if the smallest part has only one vertex (i.e., Δ=n-1). Formally, for a complete k-partite graph G=Kr1,r2,...,rk with the size of the smallest part equal to r1 ≥ 1 we have \begin{linenomath*} \begin{equation*} χi(G)= \begin{cases} Δ(G)+1 & \text{if r1=1,}
Δ(G)+2 & \text{if r1>1.} \end{cases} \end{equation*} \end{linenomath*} \noi In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is \NP-complete, thus we prove also the \NP-completeness of L(1,1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is \NP-complete for cubic graphs, which was proved in the paper \cite{HT98} (in terms of generalized dominating sets).
incidence coloring, complete multipartite graphs, semicubic graphs, subcubic graphs, \NP-completeness, L(1,1)-labelling