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/