Authors: R. Janczewski, A. Małafiejska , M. Małafiejski Title: On incidence coloring of complete multipartite and semicubic bipartite graphs Source: Discussiones Mathematicae Graph Theory Received 08.03.2016, Revised 07.10.2016, Accepted 14.10.2016, doi: 10.7151/dmgt.1995 | |
Abstract: 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=K_{r1,r2,...,rk} with the size of the smallest part equal to r_{1} ≥ 1 we have \begin{linenomath*} \begin{equation*} χ_{i}(G)= \begin{cases} Δ(G)+1 & \text{if r_{1}=1,} Δ(G)+2 & \text{if r_{1}>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). | |
Keywords: incidence coloring, complete multipartite graphs, semicubic graphs, subcubic graphs, \NP-completeness, L(1,1)-labelling | |
Links: |