Article ID Journal Published Year Pages File Type
5777668 Journal of Combinatorial Theory, Series B 2017 7 Pages PDF
Abstract
Let G be a connected graph with n vertices and m edges. Using Whitney's broken cycle theorem, we prove that if k>m−1ln⁡(1+2)≈1.135(m−1) then for every k-list assignment L of G, the number of L-colorings of G is at least that of ordinary k-colorings of G. This improves previous results of Donner (1992) and Thomassen (2009), who proved the result for k sufficiently large and k>n10, respectively.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,