Kempe changes in degenerate graphs

DOI10.1016/J.EJC.2023.103802MaRDI QIDQ6563986zbMATH OpenFDO

Authors Marthe Bonamy, Vincent Delecroix, Clément Legrand-Duchesne

Publication date 28 June 2024

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

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103802

zbMATH Keywords

\(k\)-coloringsbounded maximum average degreedegree boundslist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• Diameter of colorings under Kempe changes
• Diameter of colorings under Kempe changes
• Kempe equivalence of colourings of cubic graphs
• Kempe equivalence of colourings of cubic graphs
• Kempe equivalent list colorings

Cites work

• A linear time algorithm for finding tree-decompositions of small treewidth
• A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm
• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• A polynomial version of Cereceda's conjecture
• Algorithmic Aspects of Vertex Elimination on Graphs
• Brooks' Theorem and Beyond
• Diameter of colorings under Kempe changes
• Fast recoloring of sparse graphs
• 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
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• On an estimate of the chromatic class of a \(p\)-graph
• Recoloring graphs via tree decompositions
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The complexity of change

Cited in

(3)

• Kempe equivalent list colorings
• Kempe equivalent list colorings revisited
• Kempe classes and almost bipartite graphs

This page was built for publication: Kempe changes in degenerate graphs

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