A note on extendable sets of colorings and rooted minors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913787541454848 |
|---|---|
| author | Dvořák, Zdeněk Swart, Jan M. |
| author_facet | Dvořák, Zdeněk Swart, Jan M. |
| contents | DeVos and Seymour (2003) proved that for every set $C$ of 3-colorings of a set $X$ of vertices, there exists a plane graph $G$ with vertices of $X$ incident with the outer face such that a 3-coloring of $X$ extends to a 3-coloring of $G$ if and only if it belongs to $C$. We prove a generalization of this claim for $k$-colorings of $X$-rooted-$K_{k+1}$-minor-free $K_{k+2}$-minor-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on extendable sets of colorings and rooted minors Dvořák, Zdeněk Swart, Jan M. Combinatorics 05C15 DeVos and Seymour (2003) proved that for every set $C$ of 3-colorings of a set $X$ of vertices, there exists a plane graph $G$ with vertices of $X$ incident with the outer face such that a 3-coloring of $X$ extends to a 3-coloring of $G$ if and only if it belongs to $C$. We prove a generalization of this claim for $k$-colorings of $X$-rooted-$K_{k+1}$-minor-free $K_{k+2}$-minor-free graphs. |
| title | A note on extendable sets of colorings and rooted minors |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2504.07764 |