Colorful minors

Prelegent(ci)

Evangelos Protopapas

Język referatu

angielski

Termin

6 marca 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

Colorful minors is a recently introduced notion which generalizes the concept of (rooted) graph minors. A q-colorful graph is a graph in which each vertex is equipped with a (possibly empty) subset among a set of q fixed colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing for the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with annotated vertex sets.

In this talk, I will present three core structure theorems for colorful graphs excluding a fixed colorful minor. The first concerns excluding an arbitrary colorful graph. The other two concern excluding a planar colorful graph with two distinct assumptions on how the annotated sets are distributed within it. These results reveal that a more refined structural landscape appears when exclusion not only depends on the structure of the underlying graph but also the way the colored vertices interact with that structure.

---