Back to Search
Start Over
Kempe Equivalent List Edge-Colorings of Planar Graphs
- 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 :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2110.06191
- Document Type :
- Working Paper