Seminar of Graph Theory - František Kardoš (26.02.2026)

Thursday 26.2.2026 at 9:50, Lecture room M 213

---

František Kardoš:
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 K5-minor-free graphs. Correspondence colorings generalize list colorings as follows. Given a graph G and a positive integer t, a correspondence t-cover M assigns to each v ∈ V (G) a set of allowable colors {1_v, . . . , t_v} and to each edge vw ∈ E(G) a matching between {1_v, . . . , t_v} and {1_w, . . . , t_w}. An M-coloring φ picks for each vertex v a color φ(v) (from the set {1_v, . . . , t_v}) such that for each edge vw ∈ E(G) the colors φ(v), φ(w) are not matched to each other. Two M-colorings φ₁, φ₂ of G are disjoint if φ₁(v)≠ φ₂(v) for all v ∈ V (G). For every K5-minor-free graph G and every correspondence 6-cover M of G, we construct 3 pairwise disjoint M-colorings φ₁, φ₂, φ₃. In contrast, we provide examples of K5-minor-free graphs and correspondence 5-covers M that do not admit 3 disjoint M-colorings.

More information

---