The list 2-distance coloring of sparse graphs (Q776639)

Some relations between the maximum degree of a graph and the 2-distance chromatic number are proved. Motivated by the \textit{G. Wegner}'s conjecture proposed in [Graphs with given diameter and a coloring problem. Techn. Rep., Univ. Dortmond (1977)], the authors study the 2-distance chromatic number problem and use the sparseness of a graph together with the maximum degree to estimate the 2-distance chromatic number. The authors prove three results in Theorem 1, Theorem 2, and Theorem 3. The authors prove the results by studying structural properties of graphs and applying the discharging method. In Section 3, the authors prove Theorem 1. They first study some structural properties of the minimal counterexample, then they use the discharging method and give the discharging rules R1--R5. They design these discharging rules to redistribute charges such that the total amount of charges has not changed. They get a new charge function and derive a contradiction with the sparseness assumption. In Section 4, the authors prove Theorem 2. Similar to the proof of Theorem 1, they first study some structural properties of the minimal counterexample, then they use the discharging method to derive a contradiction. In Section 5, the authors prove Theorem 3 by studying the structural properties of the minimal counterexample, then using the discharging method. To summarize, the paper is contributive to Wegner's conjecture proposed in [loc. cit.], and is inspiring on how to use the discharging method to give new estimations of chromatic numbers. For the entire collection see [Zbl 1432.90005].