6 papers
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…
Non-crossing -graphs: a generalization of proper interval graphs admitting FPT algorithms
Flavia Bonomo-Braberman, Nick Brettell, Noleen Köhler +2
We prove new parameterized complexity results for the FO Model Checking problem on a well-known generalization of interval and circular-arc graphs: the class of -graphs, for any…
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…