6 papers
Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarsky, Yiting Jiang +2
In this paper, we prove that a graph with no -subgraph and twin-width has -admissibility and -coloring numbers bounded from above by an exponential function…
Enumerating minimal dominating sets in -free graphs and variants
Marthe Bonamy, Oscar Defrain, Marc Heinrich +2
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…
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…
A tight Erdős-Pósa function for planar minors
Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret +1
Let be a planar graph. By a classical result of Robertson and Seymour, there is a function such that for all and all graphs …
Packing and covering induced subdivisions
O-joung Kwon, Jean-Florent Raymond
A class of graphs has the induced Erdős-Pósa property if there exists a function such that for every graph and every positive integer , contains either…
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…