Strengthening a Theorem of Meyniel

DOI10.1137/22M1474394MaRDI QIDQ6158364zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

planar graphcoloringreconfiguration

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(4)

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

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)