13 citations · 26 across the 17 of their papers we have counts for
17 papers
Tree-partitions and small-spread tree-decompositions
Marc Distel, Neel Kaul, Raj Kaul +1
Tree-decompositions and treewidth are of fundamental importance in structural and algorithmic graph theory. The "spread" of a tree-decomposition is the minimum integer such tha…
A coarse Gallai theorem
Marc Distel, Ugo Giocanti, Jędrzej Hodor +2
We prove that there exist functions and such that for all positive integers and , for every graph and every subset of the vertices of , either contain…
Small counterexamples to the fat minor conjecture
Sandra Albrechtsen, Marc Distel, Agelos Georgakopoulos
We narrow the gap between the family of graphs that do and the family of graphs that do not satisfy the fat minor conjecture by obtaining much simpler counterexamples than were pre…
An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth
Marc Distel
Quasi-isometry is a measure of how similar two graphs are at `large-scale'. Nguyen, Scott, and Seymour [arXiv:2501.09839] and Hickingbotham [arXiv:2501.10840] independently gave a…
Excluding as a fat minor
Sandra Albrechtsen, Marc Distel, Agelos Georgakopoulos
We prove that for every , the graph satisfies the fat minor conjecture of Georgakopoulos and Papasoglu: for every there exist $M,A\in…
Graphs Excluding a Minor in Blowups of Treewidth 3 Graphs
Marc Distel
Alon, Seymour, and Thomas [J. Amer. Math. Soc. 1990] famously showed that every -vertex -minor-free graph has treewidth . Recently, Distel, Dujmović, Eppstei…
An improved quasi-isometry between graphs of bounded cliquewidth and graphs of bounded treewidth
Marc Distel
Cliquewidth is a dense analogue of treewidth. It can be deduced from recent results by Hickingbotham [arXiv:2501.10840] and Nguyen, Scott, and Seymour [arXiv:2501.09839] that graph…
Treewidth 2 in the Planar Graph Product Structure Theorem
Marc Distel, Kevin Hendrey, Nikolai Karol +2
We prove that every planar graph is contained in for some graphs and both with treewidth 2. This resolves a question of Liu, Norin and W…
Treewidth, Hadwiger Number, and Induced Minors
Rutger Campbell, James Davies, Marc Distel +7
Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence o…
Proper Minor-Closed Classes in Blowups of Fans
Marc Distel
Dujmović et al. [arXiv:2407.05936] showed that any -vertex planar graph is contained in a -blowup of a fan, and asked if the same holds for any -vertex…
Proper Minor-Closed Classes of Graphs have Assouad-Nagata Dimension 2
Marc Distel
Asymptotic dimension and Assouad-Nagata dimension are measures of the large-scale shape of a class of graphs. Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott [J. Eur. M…
Powers of planar graphs, product structure, and blocking partitions
Marc Distel, Robert Hickingbotham, Michał T. Seweryn +1
We prove that the -power of any planar graph is contained in for some graph with bounded treewidth, some path , and some functio…
Product structure extension of the Alon--Seymour--Thomas theorem
Marc Distel, Vida Dujmović, David Eppstein +6
Alon, Seymour and Thomas [1990] proved that every -vertex graph excluding as a minor has treewidth less than . Illingworth, Scott and Wood [2022] recently…
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…
Tree-Partitions with Small Bounded Degree Trees
Marc Distel, David R. Wood
A "tree-partition" of a graph is a partition of such that identifying the vertices in each part gives a tree. It is known that every graph with treewidth and maximum…
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…
Improved product structure for graphs on surfaces
Marc Distel, Robert Hickingbotham, Tony Huynh +1
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph with Euler genus there is a graph with treewidth at most 4 and a path suc…