Fast recoloring of sparse graphs

DOI10.1016/j.ejc.2015.08.001zbMath1327.05189arXiv1411.6997OpenAlexW2964083169MaRDI QIDQ896058

Guillem Perarnau, Nicolas Bousquet

Publication date: 11 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Related Items (22)

Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ A polynomial version of Cereceda's conjecture ⋮ In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent ⋮ List-recoloring of sparse graphs ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Recoloring graphs via tree decompositions ⋮ Digraph redicolouring ⋮ On the connectivity of proper colorings of random graphs and hypergraphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Reconfiguring colorings of graphs with bounded maximum average degree ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs ⋮ Recoloring graphs of treewidth 2 ⋮ Unnamed Item ⋮ A Thomassen-type method for planar graph recoloring ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Distributed Recoloring ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Reconfiguration of dominating sets
• Sparsity. Graphs, structures, and algorithms
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Recoloring graphs via tree decompositions
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Fast recoloring of sparse graphs