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/

[1] I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989) 11–22. doi:10.1016/0012-365X(89)90073-3

[2] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992) 375–380. doi:10.1007/BF01305230

[3] R.A. Brualdi and J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51–58. doi:10.1016/0012-365X(93)90286-3

[4] T. Calamoneri, The L ( h, k )- labelling problem: an updated survey and annotated bibliography, Department of Computer Science, University of Rome (2014) 1–54, a manuscript.

[5] D.L. Chen, X.K. Liu and S.D. Wang, The incidence chromatic number and the incidence coloring conjecture of graphs, Math. Econ. 15 (1998) 47–51.

[6] D.L. Chen, P.C.B. Lam and W.C. Shiu, On incidence coloring for some cubic graphs, Discrete Math. 252 (2002) 259–266. doi:10.1016/S0012-365X(01)00457-5

[7] M.H. Dolama, E. Sopena and X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. 283 (2004) 121–128. doi:10.1016/j.disc.2004.01.015

[8] M.H. Dolama and E. Sopena, On the maximum average degree and the incidence chromatic number of a graph, Discrete Math. Theor. Comput. Sci. 7 (2005) 203–216.

[9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York, 1979).

[10] B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math. 163 (1997) 275–278. doi:10.1016/0012-365X(95)00342-T

[11] J. Guo, X. Meng and B. Su, Incidence coloring of pseudo-Halin graphs, Discrete Math. 312 (2012) 3276–3282. doi:10.1016/j.disc.2012.07.024

[12] P. Heggernes and J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998) 128–143.

[13] X. Li and J. Tu, NP-completeness of 4-incidence colorability of semi-cubic graphs, Discrete Math. 308 (2008) 1334–1340. doi:10.1016/j.disc.2007.03.076

[14] M. Maydanskiy, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005) 131–141. doi:10.1016/j.disc.2005.02.003

[15] K. Nakprasit and K. Nakprasit, Incidence colorings of the powers of cycles, Int. J. Pure Appl. Math. 76 (2012) 143–148.

[16] A.C. Shiau, T.-H. Shiau and Y.-L. Wang, Incidence coloring of Cartesian product graphs, Inform. Process. Lett. 115 (2015) 765–768. doi:10.1016/j.ipl.2015.05.002

[17] W.C. Shiu and P.K. Sun, Invalid proofs on incidence coloring, Discrete Math. 308 (2008) 6575–6580. doi:10.1016/j.disc.2007.11.030

[18] J. Wu, Some results on the incidence coloring number of a graph, Discrete Math. 309 (2009) 3866–3870. doi:10.1016/j.disc.2008.10.027

[19] X. Liu and Y. Li, The incidence chromatic number of some graph, Int. J. Math. Math. Sci. 5 (2005) 803–813. doi:10.1155/IJMMS.2005.803