Back to Search Start Over

Kempe Equivalent List Edge-Colorings of Planar Graphs

Authors :
Cranston, Daniel W.
Publication Year :
2021

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)\ge 9$ 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)\ge 15$ 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.<br />Comment: 15 pages, 5 figures, 2 page appendix; to appear in Discrete Math (special issue in honor of Landon Rabern)

Subjects

Subjects :
Mathematics - Combinatorics
05C15

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2110.06191
Document Type :
Working Paper