کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653339 | 1632766 | 2016 | 11 صفحه PDF | دانلود رایگان |
In this paper, we show that for every graph of maximum average degree bounded away from dd and any two (d+1)(d+1)-colorings of it, one can transform one coloring into the other one within a polynomial number of vertex recolorings so that, at each step, the current coloring is proper. In particular, it implies that we can transform any 88-coloring of a planar graph into any other 88-coloring with a polynomial number of recolorings. These results give some evidence on a conjecture of Cereceda et al. (2009) which asserts that any (d+2)(d+2) coloring of a dd-degenerate graph can be transformed into any other one using a polynomial number of recolorings.We also show that any (2d+2)(2d+2)-coloring of a dd-degenerate graph can be transformed into any other one with a linear number of recolorings.
Journal: European Journal of Combinatorics - Volume 52, Part A, February 2016, Pages 1–11