Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2211.16728 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910324796424192 |
|---|---|
| author | Chakraborty, Dibyayan Feghali, Carl Mahmoud, Reem |
| author_facet | Chakraborty, Dibyayan Feghali, Carl Mahmoud, Reem |
| contents | A \emph{Kempe chain} on colors $a$ and $b$ is a component of the subgraph induced by colors $a$ and $b$. A \emph{Kempe change} is the operation of interchanging the colors of some Kempe chain. For a list-assignment $L$ and an $L$-coloring $φ$, a Kempe change is \emph{$L$-valid} for $φ$ if performing the Kempe change yields another $L$-coloring. Two $L$-colorings are \emph{$L$-equivalent} if we can form one from the other by a sequence of $L$-valid Kempe changes. A \emph{degree-assignment} is a list-assignment $L$ such that $L(v)\ge d(v)$ for every $v\in V(G)$. Cranston and Mahmoud (\emph{Combinatorica}, 2023) asked: For which graphs $G$ and degree-assignment $L$ of $G$ is it true that all the $L$-colorings of $G$ are $L$-equivalent? We prove that for every 4-connected graph $G$ which is not complete and every degree-assignment $L$ of $G$, all $L$-colorings of $G$ are $L$-equivalent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_16728 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Kempe Equivalent List Colorings Revisited Chakraborty, Dibyayan Feghali, Carl Mahmoud, Reem Combinatorics 05C15 A \emph{Kempe chain} on colors $a$ and $b$ is a component of the subgraph induced by colors $a$ and $b$. A \emph{Kempe change} is the operation of interchanging the colors of some Kempe chain. For a list-assignment $L$ and an $L$-coloring $φ$, a Kempe change is \emph{$L$-valid} for $φ$ if performing the Kempe change yields another $L$-coloring. Two $L$-colorings are \emph{$L$-equivalent} if we can form one from the other by a sequence of $L$-valid Kempe changes. A \emph{degree-assignment} is a list-assignment $L$ such that $L(v)\ge d(v)$ for every $v\in V(G)$. Cranston and Mahmoud (\emph{Combinatorica}, 2023) asked: For which graphs $G$ and degree-assignment $L$ of $G$ is it true that all the $L$-colorings of $G$ are $L$-equivalent? We prove that for every 4-connected graph $G$ which is not complete and every degree-assignment $L$ of $G$, all $L$-colorings of $G$ are $L$-equivalent. |
| title | Kempe Equivalent List Colorings Revisited |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2211.16728 |