Injective Colorings of Graphs with Low Average Degree
Let mad (G) denote the maximum average degree (over all subgraphs) of G and let chi (i) (G) denote the injective chromatic number of G. We prove that if Delta >= 4 and mad (G) < 14/5, then chi i (G) <= Delta +2. When Delta = 3, we show that mad (G) < 36/13 implies chi i (G) <= 5. In contrast, we give a graph G with Delta = 3, mad (G) = 36/13, and chi (i) (G)=6.
injective coloring maximum average degree discharging method list coloring