Disjoint Correspondence Colorings for $K_5$-Minor-free Graphs

Abstract

Thomassen famously proved that every planar graph is 5-choosable. We explore variants of this result, focusing on finding disjoint correspondence colorings, in the more general class of $K_5$-minor-free graphs. Correspondence colorings generalize list colorings as follows. Given a graph $G$ and a positive integer $t$, a correspondence $t$-cover $\text{M}$ assigns to each $v\in V(G)$ a set of allowable colors $\{1_v,\dots ,t_v\}$ and to each edge $vw\in E(G)$ a matching between $\{1_v,\dots ,t_v\}$ and $\{1_w,\dots ,t_w\}$. An $\text{M}$-coloring $\phi$ picks for each vertex $v$ a color $\phi (v)$ (from the set $\{1_v,\dots ,t_v\}$) such that for each edge $vw\in E(G)$ the colors $\phi (v),\phi (w)$ are not matched to each other. Two $\text{M}$-colorings ${\phi }_1,{\phi }_2$ of $G$ are called disjoint if ${\phi }_1(v)\ne {\phi }_2(v)$ for all $v\in V(G)$. For every $K_5$-minor-free graph $G$ and every correspondence 6-cover $\text{M}$ of $G$, we construct 3 pairwise disjoint $\text{M}$-colorings ${\phi }_1,{\phi }_2,{\phi }_3$. In contrast, we provide examples of $K_5$-minor-free graphs and correspondence 5-covers $\text{M}$ that do not admit 3 disjoint $\text{M}$-colorings.

9 pages, 1 figure