Strengthening a Theorem of Meyniel

DOI10.1137/22M1474394zbMATH Open1515.05066arXiv2201.07595OpenAlexW4376867173WikidataQ121945083 ScholiaQ121945083MaRDI QIDQ6158364FDOQ6158364

Authors: Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne, Théo Pierron 

Publication date: 31 May 2023

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

Abstract: For an integer $kgeq1$ and a graph $G$, let $mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $alpha$ and~$$ whenever the coloring~$$ can be obtained from $alpha$ by a single Kempe change. A theorem of Meyniel from 1978 states that $mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $mathcal{K}_5(G)$ has diameter $O(|V(G){|}^c)$ for every planar graph $G$.

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

Recommendations

• Diameter of colorings under Kempe changes
• Diameter of colorings under Kempe changes
• Recoloring Planar Graphs of Girth at Least Five
• Toward Cereceda's conjecture for planar graphs
• A Thomassen-type method for planar graph recoloring

zbMATH Keywords

planar graphcoloringreconfiguration

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms
• The four-colour theorem
• Geometric coloring theory
• Title not available (Why is that?)
• Every Planar Map is Four Colorable
• Kempe classes and the Hadwiger conjecture
• Les 5-colorations d'un graphe planaire forment une classe de commutation unique
• A polynomial version of Cereceda's conjecture
• Akempic triangulations with 4 odd vertices
• Paths between colourings of sparse graphs
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Toward Cereceda's conjecture for planar graphs

Cited In (4)

• Kempe classes and almost bipartite graphs
• Recoloring Planar Graphs of Girth at Least Five
• A strengthening of the Assmus-Mattson theorem
• A strengthening of Men'shov's theorem on correction

This page was built for publication: Strengthening a Theorem of Meyniel

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