4 papers
The Local Structure Theorem for Graph Minors with finite index
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
The Local Structure Theorem (LST) for Graph Minors roughly states that for every -minor-free graph that contains a sufficiently large wall , there is a small vertex subse…
Twin-width one
Jungho Ahn, Hugo Jacob, Noleen Köhler +3
We investigate the structure of graphs of twin-width at most , and obtain the following results: - Graphs of twin-width at most are permutation graphs. In particular they ha…
Obstructions to Erdős-Pósa Dualities for Minors
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
Let and be minor-closed graph classes. The pair is an Erdős-Pósa pair (EP-pair) if there is a function where, for every and ever…
Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for…