6 papers · 1 filter
Subdivided expanders and counterexamples to the Tree Product Conjecture
Andrea Munaro
Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood (2023) conjectured that graphs of degree- polynomial growth can be embedded into the strong product of trees,…
Graph Classes Closed under Self-intersection
Konrad K. Dabrowski, Vadim V. Lozin, Martin MilaniÄ +3
A graph class is monotone if it is closed under taking subgraphs. It is known that a monotone class defined by finitely many obstructions has bounded treewidth if and only if one o…
Layered tree-independence number and clique-based separators
Clément Dallard, Martin MilaniÄ, Andrea Munaro +1
Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublin…
Maximum list -colorable induced subgraphs in -free graphs
Esther Galby, Paloma T. Lima, Andrea Munaro +1
We show that, for every fixed positive integers and , \textsc{Max-Weight List -Colorable Induced Subgraph} admits a polynomial-time algorithm on -free graphs. This…
Comparing Width Parameters on Graph Classes
Nick Brettell, Andrea Munaro, Daniël Paulusma +1
We study how the relationship between non-equivalent width parameters changes once we restrict to some special graph class. As width parameters, we consider treewidth, clique-width…
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Clément Dallard, Matjaž Krnc, O-joung Kwon +4
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes de…