12 citations · 47 across the 20 of their papers we have counts for
12 papers · 1 filter
Excluding Single-Crossing Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht
\noindent By a seminal result of Valiant, computing the permanent of -matrices is, in general, -hard. In 1913 Pólya asked for which -matrices it is…
A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou, Sebastian Wiederrecht
A major step in the graph minors theory of Robertson and Seymour is the transition from the Grid Theorem which, in some sense uniquely, describes areas of large treewidth within a…
Two Disjoint Alternating Paths in Bipartite Graphs
Archontia C. Giannopoulou, Sebastian Wiederrecht
A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B and a cycle C in B is called conform…
Excluding a Planar Matching Minor in Bipartite Graphs
Archontia C Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bi…
Braces of Perfect Matching Width 2
Archontia C. Giannopoulou, Meike Hatzel, Sebastian Wiederrecht
Perfect matching width is a treewidth-like parameter designed for graphs with perfect matchings. The concept was originally introduced by Norine for the study of non-bipartite Pfaf…
A Menger-like property of tree-cut width
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1
In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness [A Menger-l…
Matching Connectivity: On the Structure of Graphs with Perfect Matchings
Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
We introduce the concept of matching connectivity as a notion of connectivity in graph admitting perfect matchings which heavily relies on the structural properties of those matchi…
Packing and Covering Immersion Models of Planar subcubic Graphs
Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1
A graph is an immersion of a graph if can be obtained by some sugraph after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bb…
The Structure of -Immersion-Free Graphs
Rémy Belmonte, Archontia Giannopoulou, Daniel Lokshtanov +1
We study the structure of graphs that do not contain the wheel on 5 vertices W4 as an immersion, and show that these graphs can be constructed via 1, 2, and 3-edge-sums from subcub…
Excluding Graphs as Immersions in Surface Embedded Graphs
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
We prove a structural characterization of graphs that forbid a fixed graph as an immersion and can be embedded in a surface of Euler genus . In particular, we prove that a g…
Forbidding Kuratowski Graphs as Immersions
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph contains a graph as a topolo…
Optimizing the Graph Minors Weak Structure Theorem
Archontia C. Giannopoulou, Dimitrios M. Thilikos
One of the major results of [N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65--110, 1995], also known as the weak…