Fast recoloring of sparse graphs

Nicolas Bousquet, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)
225 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1-11
JournalEuropean Journal of Combinatorics
Volume52
Issue numberA
Early online date7 Sept 2015
DOIs
Publication statusPublished - Feb 2016

Fingerprint

Dive into the research topics of 'Fast recoloring of sparse graphs'. Together they form a unique fingerprint.

Cite this