Incidence coloring-cold cases
František Kardoš, Mária Maceková, Martina Mockovčiaková, Éric Sopena, Roman Soták · Discussiones Mathematicae Graph Theory · 2018
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 346 F. Kardoš, M. Maceková, M. Mockovčiaková, É. Sopena and ... most ∆(G) + 2 for any graph G with mad(G) < 3 and ∆(G) = 4, and for any graph with mad(G) < 10 3 and ∆(G) ≥ 8.