Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653498 | European Journal of Combinatorics | 2014 | 10 Pages |
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
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou,