Kempe equivalence of 4‐critical planar graphs

DOI10.1002/JGT.22908MaRDI QIDQ6047640zbMATH OpenOpenAlexFDO

Authors Carl Feghali

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

four-critical graphKempe equivalenceplanar graph

Mathematics Subject Classification ID

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

Abstract: Answering a question of Mohar from 2007, we show that for every $4$-critical planar graph, its set of $4$-colorings is a Kempe class.

Recommendations

• scientific article; zbMATH DE number 5130739
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs
• Planar 4-critical graphs with four triangles
• scientific article; zbMATH DE number 3970775
• Large faces in 4-critical planar graphs with minimum degree 4

Cites work

• A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm
• A not 3-choosable planar graph without 3-cycles
• A reconfigurations analogue of Brooks' theorem and its consequences
• A short list color proof of Grötzsch's theorem
• Akempic triangulations with 4 odd vertices
• Connectedness of the graph of vertex-colourings
• Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
• Diameter of colorings under Kempe changes
• Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus
• Every planar graph is 5-choosable
• Geometric coloring theory
• scientific article; zbMATH DE number 5130739 (Why is no real title available?)
• Improved bounds for sampling colorings
• Kempe classes and the Hadwiger conjecture
• Kempe equivalence of colourings of cubic graphs
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs
• Les 5-colorations d'un graphe planaire forment une classe de commutation unique
• On 4-critical planar graphs with high edge density
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Shortest Reconfiguration of Colorings Under Kempe Changes
• The complexity of change

Cited in

(4)

• 4-critical 4-valent planar graphs constructed with crowns.
• Kempe equivalence of almost bipartite graphs
• Kempe equivalent list colorings revisited
• Kempe classes and almost bipartite graphs

This page was built for publication: Kempe equivalence of 4‐critical planar graphs

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