Recoloring graphs of treewidth 2

DOI10.1016/J.DISC.2021.112553MaRDI QIDQ6356621arXivFDO

Authors Valentin Bartier, Nicolas Bousquet, Marc Heinrich

Publication date 21 December 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2021.112553

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

arXiv classification

cs.DMmath.CO

Abstract: Two (proper) colorings of a graph are adjacent if they differ on exactly one vertex. Jerrum proved that any $(d+2)$-coloring of any d-degenerate graph can be transformed into any other via a sequence of adjacent colorings. A result of Bonamy et al. ensures that a shortest transformation can have a quadratic length even for $d=1$. Bousquet and Perarnau proved that a linear transformation exists for between $(2d+2)$-colorings. It is open to determine if this bound can be reduced. In this note, we prove that it can be reduced for graphs of treewidth 2, which are 2-degenerate. There exists a linear transformation between 5-colorings. It completes the picture for graphs of treewidth 2 since there exist graphs of treewidth 2 such a linear transformation between 4-colorings does not exist.

This page was built for publication: Recoloring graphs of treewidth 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356621)