Kempe equivalent list edge-colorings of planar graphs

DOI10.1016/J.DISC.2022.113180MaRDI QIDQ6091809zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston

Publication date 27 November 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

choosabilityedge-coloringplanar graphsdischarginglist-coloringKempe swaps

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: For a list assignment $L$ and an $L$-coloring $varphi$, a Kempe swap in $varphi$ is emph{$L$-valid} if it yields another $L$-coloring. Two $L$-colorings are emph{$L$-equivalent} if we can form one from another by a sequence of $L$-valid Kempe swaps. And a graph $G$ is emph{$L$-swappable} if every two of its $L$-colorings are $L$-equivalent. We consider $L$-swappability of line graphs of planar graphs with large maximum degree. Let $G$ be a planar graph with $Delta(G)ge9$ and let $H$ be the line graph of $G$. If $L$ is a $(Delta(G)+1)$-assignment to $H$, then $H$ is $L$-swappable. Let $G$ be a planar graph with $Delta(G)ge15$ and let $H$ be the line graph of $G$. If $L$ is a $Delta(G)$-assignment to $H$, then $H$ is $L$-swappable. The first result is analogous to one for $L$-choosability by Borodin, which was later strengthened by Bonamy. The second result is analogous to another for $L$-choosability by Borodin, which was later strengthened by Borodin, Kostochka, and Woodall.

Recommendations

• Kempe equivalent list colorings
• Kempe equivalent list colorings revisited
• Sufficient conditions for a planar graph to be list edge \(\Delta \)-colorable and list totally \((\Delta +1)\)-colorable
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs

Cites work

• scientific article; zbMATH DE number 5130739 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
• Kempe classes and the Hadwiger conjecture
• Kempe equivalence of colourings of cubic graphs
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs
• List edge and list total colourings of multigraphs
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Planar graphs with \(\Delta\geq 8\) are (\(\Delta+1\))-edge-choosable
• Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
• Reconfiguration of list edge-colorings in a graph
• Solution of Vizing's problem on interchanges for the case of graphs with maximum degree 4 and related results

Cited in

(3)

• Kempe equivalent list colorings
• scientific article; zbMATH DE number 5130739 (Why is no real title available?)
• Kempe classes and almost bipartite graphs

This page was built for publication: Kempe equivalent list edge-colorings of planar graphs

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