15 citations · 73 across the 38 of their papers we have counts for
5 papers · 1 filter
Twin-width of random graphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +2
We investigate the twin-width of the Erdős-Rényi random graph . We unveil a surprising behavior of this parameter by showing the existence of a constant su…
Rainbow saturation for complete graphs
Debsoumya Chakraborti, Kevin Hendrey, Ben Lund +1
We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph is called -rainbow saturated if does not contain a rainbow copy…
Graphs of Linear Growth have Bounded Treewidth
Rutger Campbell, Marc Distel, J. Pascal Gollin +5
A graph class has linear growth if, for each graph and every positive integer , every subgraph of with radius at most contains v…
A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, O-joung Kwon +2
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such…
Product structure of graph classes with bounded treewidth
Rutger Campbell, Katie Clinch, Marc Distel +8
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end…