Recoloring graphs of treewidth 2

DOI10.1016/j.disc.2021.112553OpenAlexW3197211811MaRDI QIDQ2231701

Valentin Bartier, Nicolas Bousquet, Marc Heinrich

Publication date: 30 September 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.11459

zbMATH Keywords

linear transformationtreewidthrecoloringCereceda's conjecture

Mathematics Subject Classification ID

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

Related Items (2)

Recoloring Planar Graphs of Girth at Least Five ⋮ Parameterized complexity of reconfiguration of atoms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast recoloring of sparse graphs
• Mixing 3-colourings in bipartite graphs
• Paths between colourings of sparse graphs
• Flipping edge-labelled triangulations
• Reconfiguring colorings of graphs with bounded maximum average degree
• An update on reconfiguring 10-colorings of planar graphs
• The complexity of change
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Improved Bounds for Randomly Sampling Colorings via Linear Programming
• A linear time algorithm for finding tree-decompositions of small treewidth

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