Geodesic
Incidence Coloring—Cold Cases
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 345-354.

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

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (i) v = u, (ii) e = f, or (iii) edge vu is from the set e, f. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. The minimum number of colors needed for incidence coloring of a graph is called the incidence chromatic number. It was proved that at most Δ(G) + 5 colors are enough for an incidence coloring of any planar graph G except for Δ(G) = 6, in which case at most 12 colors are needed. It is also known that every planar graph G with girth at least 6 and Δ(G) ≥ 5 has incidence chromatic number at most Δ(G) + 2. In this paper we present some results on graphs regarding their maximum degree and maximum average degree. We improve the bound for planar graphs with Δ(G) = 6. We show that the incidence chromatic number is at most Δ(G) + 2 for any graph G with mad(G) lt; 3 and Δ(G) = 4, and for any graph with mad(G) lt;103 and Δ(G) ≥ 8.
Keywords: incidence coloring, incidence chromatic number, planar graph, maximum average degree 
@article{DMGT_2020_40_1_a23,
     author = {Kardo\v{s}, Franti\v{s}ek and Macekov\'a, M\'aria and Mockov\v{c}iakov\'a, Martina and Sopena, \'Eric and Sot\'ak, Roman},
     title = {Incidence {Coloring{\textemdash}Cold} {Cases}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {345--354},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a23/}
}
TY  - JOUR
AU  - Kardoš, František
AU  - Maceková, Mária
AU  - Mockovčiaková, Martina
AU  - Sopena, Éric
AU  - Soták, Roman
TI  - Incidence Coloring—Cold Cases
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 345
EP  - 354
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a23/
LA  - en
ID  - DMGT_2020_40_1_a23
ER  - 
%0 Journal Article
%A Kardoš, František
%A Maceková, Mária
%A Mockovčiaková, Martina
%A Sopena, Éric
%A Soták, Roman
%T Incidence Coloring—Cold Cases
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 345-354
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a23/
%G en
%F DMGT_2020_40_1_a23
Kardoš, František; Maceková, Mária; Mockovčiaková, Martina; Sopena, Éric; Soták, Roman. Incidence Coloring—Cold Cases. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 345-354. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a23/

[1] M. Bonamy, B. Lévêque and A. Pinlou, 2 -distance coloring of sparse graphs, J. Graph Theory 77 (2014) 190–218. doi:10.1002/jgt.21782

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

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

[4] S.L. Hakimi, J. Mitchem and E. Schmeichel, Star arboricity of graphs, Discrete Math. 149 (1996) 93–98. doi:10.1016/0012-365X(94)00313-8

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

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

[7] D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B 83 (2001) 201–212. doi:10.1006/jctb.2001.2047

[8] D. Yang, Fractional incidence coloring and star arboricity of graphs, Ars Combin. 105 (2012) 213–224.