Disjoint Correspondence Colorings for K 5 K_{5} -Minor-free Graphs

Wouter Cames van Batenburg, Daniel W. Cranston, František Kardoš · 2026

Read Disjoint Correspondence Colorings for K 5 K_{5} -Minor-free Graphs by Wouter Cames van Batenburg, Daniel W. Cranston, František Kardoš (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-16692.txt.

Description

Wouter Cames van Batenburg, Daniel Cranston, and František Kardoš extend a classic coloring result to disjoint correspondence colorings. Thomassen proved every planar graph is 5-choosable. Correspondence coloring generalizes list coloring: each vertex gets a set of color copies, and each edge pairs copies that must not match. Two colorings are disjoint when they never give the same copy at any vertex.

For every K5-minor-free graph and every correspondence 6-cover, the authors build three pairwise disjoint colorings. In contrast, they give K5-minor-free graphs with correspondence 5-covers that admit no three disjoint colorings. Graph theorists get a sharp boundary: six copies suffice for triple disjoint colorings, while five do not always.

Catalog record

CREATORWouter Cames van Batenburg, Daniel W. Cranston, František Kardoš
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-16692

Browse the full library · About the Tower of Babel