2-Distance Coloring of Sparse Graphs

For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than 7/3 and maximum degree Delta at least 4 are 2-distance (Delta + 1)-colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than 12/5 (resp. 5/2, 18/7) and maximum degree Delta at least 5 (resp. 6, 8) are list 2-distance (Delta + 1)-colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than 14/5 and with large enough maximum degree Delta (depending only on m) can be list 2-distance (Delta + 1)-colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2-distance (Delta + 1)-colored: the question of what happens between 14/5 and 3 remains open. We prove also that any graph with maximum average degree m < 4 can be list 2-distance (Delta + C)-colored (C depending only on m). It is optimal as there exist graphs with arbitrarily largemaximum degree and maximum average degree less than 4 that cannot be 2-distance colored with less than 3 Delta/2 colors. Most of the above results can be transposed to injective list coloring with one color less. (C) 2014 Wiley Periodicals, Inc.