Kempe equivalence of almost bipartite graphs

MaRDI QIDQ6072049zbMATH OpenFDO

Authors Akihiro Higashitani, Naoki Matsumoto

Publication date 29 November 2023

Full work available at URL https://arxiv.org/abs/2207.13244, http://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p203.pdf

zbMATH Keywords

color-critical graphsKempe changes

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Kempe classes and almost bipartite graphs
• Kempe equivalence of colourings of cubic graphs
• Diameter of colorings under Kempe changes
• Diameter of colorings under Kempe changes
• Kempe equivalence of colourings of cubic graphs

Cites work

• A class of edge critical 4-chromatic graphs
• A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm
• Diameter of colorings under Kempe changes
• Graph theory with applications
• Improved bounds for sampling colorings
• Kempe classes and the Hadwiger conjecture
• Kempe equivalence of 4‐critical planar graphs
• Linear-time recognition of bipartite graphs plus two edges
• Mutual exclusion scheduling with interval graphs or related classes. I
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Perfectly contractile graphs
• The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges

Cited in

(1)

• Kempe classes and almost bipartite graphs

This page was built for publication: Kempe equivalence of almost bipartite graphs

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