F. Kardoı, M. Maceková, M. Mockovèiaková, É. Sopena, R. Soták
Incidence coloring-cold cases
Discussiones Mathematicae Graph Theory
Received 09.10.2017, Revised 25.04.2018, Accepted 26.04.2018, doi: 10.7151/dmgt.2140

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) <3 and Δ(G)=4, and for any graph with \mad(G) <\frac{10}{3} and Δ(G) ≥ 8.
incidence coloring, incidence chromatic number, planar graph, maximum average degree