Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949536 | Discrete Applied Mathematics | 2017 | 15 Pages |
Abstract
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 and Sopena (2005) proved that every graph with maximum average degree strictly less than 3 can be incidence colored with Î+3 colors. Recently, Bonamy et al. (2014) proved that every graph with maximum degree at least 4 and with maximum average degree strictly less than 73 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marthe Bonamy, Hervé Hocquard, Samia Kerdjoudj, André Raspaud,