Disjoint Correspondence Colorings for $K_5$-Minor-free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914337757593600 |
|---|---|
| author | van Batenburg, Wouter Cames Cranston, Daniel W. Kardoš, František |
| author_facet | van Batenburg, Wouter Cames Cranston, Daniel W. Kardoš, František |
| contents | 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 $\textbf{M}$ assigns to each $v\in V(G)$ a set of allowable colors $\{1_v,\ldots,t_v\}$ and to each edge $vw\in E(G)$ a matching between $\{1_v,\ldots,t_v\}$ and $\{1_w,\ldots,t_w\}$. An $\textbf{M}$-coloring $φ$ picks for each vertex $v$ a color $φ(v)$ (from the set $\{1_v,\ldots,t_v\}$) such that for each edge $vw\in E(G)$ the colors $φ(v),φ(w)$ are not matched to each other. Two $\textbf{M}$-colorings $φ_1,φ_2$ of $G$ are called disjoint if $φ_1(v)\neφ_2(v)$ for all $v\in V(G)$. For every $K_5$-minor-free graph $G$ and every correspondence 6-cover $\textbf{M}$ of $G$, we construct 3 pairwise disjoint $\textbf{M}$-colorings $φ_1,φ_2,φ_3$. In contrast, we provide examples of $K_5$-minor-free graphs and correspondence 5-covers $\textbf{M}$ that do not admit 3 disjoint $\textbf{M}$-colorings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16692 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Disjoint Correspondence Colorings for $K_5$-Minor-free Graphs van Batenburg, Wouter Cames Cranston, Daniel W. Kardoš, František Combinatorics 05C15, 05C10, 05C70, 05C83 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 $\textbf{M}$ assigns to each $v\in V(G)$ a set of allowable colors $\{1_v,\ldots,t_v\}$ and to each edge $vw\in E(G)$ a matching between $\{1_v,\ldots,t_v\}$ and $\{1_w,\ldots,t_w\}$. An $\textbf{M}$-coloring $φ$ picks for each vertex $v$ a color $φ(v)$ (from the set $\{1_v,\ldots,t_v\}$) such that for each edge $vw\in E(G)$ the colors $φ(v),φ(w)$ are not matched to each other. Two $\textbf{M}$-colorings $φ_1,φ_2$ of $G$ are called disjoint if $φ_1(v)\neφ_2(v)$ for all $v\in V(G)$. For every $K_5$-minor-free graph $G$ and every correspondence 6-cover $\textbf{M}$ of $G$, we construct 3 pairwise disjoint $\textbf{M}$-colorings $φ_1,φ_2,φ_3$. In contrast, we provide examples of $K_5$-minor-free graphs and correspondence 5-covers $\textbf{M}$ that do not admit 3 disjoint $\textbf{M}$-colorings. |
| title | Disjoint Correspondence Colorings for $K_5$-Minor-free Graphs |
| topic | Combinatorics 05C15, 05C10, 05C70, 05C83 |
| url | https://arxiv.org/abs/2602.16692 |