Article ID Journal Published Year Pages File Type
4653498 European Journal of Combinatorics 2014 10 Pages PDF
Abstract
We strengthen their result and prove that there exists a function f such that the square of any graph with maximum average degree m<3 and maximum degree Δ≥f(m) is list (Δ+1)-colorable. Note the planarity assumption is dropped. This bound of 3 is optimal in the sense that the above-mentioned planar graphs with girth 6 have maximum average degree less than 3 and arbitrarily large maximum degree, while their square cannot be (Δ+1)-colored. The same holds for list injective Δ-coloring.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,