Fast recoloring of sparse graphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
Pages (from-to)1-11
JournalEuropean Journal of Combinatorics
Volume52
Issue numberA
Early online date7 Sep 2015
Publication statusPublished - Feb 2016