A Thomassen-type method for planar graph recoloring

DOI10.1016/j.ejc.2021.103319zbMath1466.05048arXiv2006.09269OpenAlexW3133989664MaRDI QIDQ2033925

Zdeněk Dvořák, Carl Feghali

Publication date: 18 June 2021

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

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

zbMATH Keywords

reconfiguration graphlist coloring technique

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Recoloring Planar Graphs of Girth at Least Five ⋮ List-recoloring of sparse graphs ⋮ Optimally reconfiguring list and correspondence colourings ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles

Cites Work

• Fast recoloring of sparse graphs
• Every planar graph is 5-choosable
• Recoloring graphs via tree decompositions
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• 3-list-coloring planar graphs of girth 5
• An update on reconfiguring 10-colorings of planar graphs
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguring 10-colourings of planar graphs
• The complexity of change

This page was built for publication: A Thomassen-type method for planar graph recoloring