Geodesic
On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 107-119

Voir la notice de l'article provenant de la source Library of Science

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_r_1,r_2,...,r_k with the size of the smallest part equal to r_1 ≥ 1 we have χ_i (G)= Δ(G)+1 amp; if  r_1=1, Δ(G)+2 amp; if  r_1 gt;1. In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is 𝒩𝒫-complete, thus we prove also the 𝒩𝒫-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is 𝒩𝒫-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).
Keywords: incidence coloring, complete multipartite graphs, semicubic graphs, subcubic graphs, -completeness, L (1,1)-labelling 
@article{DMGT_2018_38_1_a8,
     author = {Janczewski, Robert and Ma{\l}afiejski, Micha{\l} and Ma{\l}afiejska, Anna},
     title = {On {Incidence} {Coloring} of {Complete} {Multipartite} and {Semicubic} {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {107--119},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a8/}
}
TY  - JOUR
AU  - Janczewski, Robert
AU  - Małafiejski, Michał
AU  - Małafiejska, Anna
TI  - On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 107
EP  - 119
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a8/
LA  - en
ID  - DMGT_2018_38_1_a8
ER  - 
%0 Journal Article
%A Janczewski, Robert
%A Małafiejski, Michał
%A Małafiejska, Anna
%T On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 107-119
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a8/
%G en
%F DMGT_2018_38_1_a8
Janczewski, Robert; Małafiejski, Michał; Małafiejska, Anna. On Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 107-119. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a8/