Seminár z teórie grafov - František Kardoš (26.02.2026)

vo štvrtok 26.2.2026 o 9:50 hod. v miestnosti M 213

---

Prednášajúci: František Kardoš

Názov prednášky: Disjoint Correspondence Colorings for K_5-Minor-free Graphs

Termín: 26.2.2026, 9:50 hod., M 213

Abstrakt:
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.

Stránka seminára

---