Degree-list Kempe equivalence for 3-connected graphs
In a proper coloring, a Kempe change interchanges two colors on a connected component of the subgraph they induce. For a fixed list assignment $L$, a Kempe change is $L$-valid if it transforms an $L$-coloring into another $L$-coloring. We prove that if $G$ is a $3$-connected graph other than a complete graph or the triangular prism, and $L$ is a list assignment with $|L(v)|\ge d_G(v)$ for every vertex $v$, then $G$ has a proper $L$-coloring and any two such colorings can be transformed into one another by a finite sequence of $L$-valid Kempe changes. This proves a conjecture of Chakraborty,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.35701
curl -X POST /api/v1/records/arxiv/2610.35701/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.35701/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'