2014/12/21 by Bonamy, Marthe, Hocquard, Hervé, Kerdjoudj, Samia +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1412.6803
An incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident with v. Two incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama et al.~\citepds05 proved that every graph with maximum average degree strictly less than 3 can be incidence colored with Δ+3 colors. Recently, Bonamy et al.~\citepBonamy proved that every graph with maximum degree at least 4 and with maximum average degree strictly less than (7)/(3) admits an incidence (Δ+1)-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between 4 and 6. In particular we prove that every graph with maximum degree at least 7 and with maximum average degree less than 4 admits an incidence (Δ+3)-coloring. This result implies that every triangle-free planar graph with maximum degree at least 7 is incidence (Δ+3)-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence (Δ+ 7)-coloring. More generally, we prove that Δ+k-1 colors are enough when the maximum average degree is less than k and the maximum degree is sufficiently large.