12 citations · 46 across the 17 of their papers we have counts for
21 papers
Odd Cycle Transversal on -free graphs
Esther Galby, Paloma T. de Lima, Andrea Munaro +1
\textsc{Odd Cycle Transversal} is a classic -hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite…
Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
Andrea Munaro
We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a…
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…
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…
Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approxim…
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…
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…
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for inde…
Non-empty intersection of longest paths in -free graphs
James A. Long, Kevin G. Milans, Andrea Munaro
We make progress toward a characterization of the graphs such that every connected -free graph has a longest path transversal of size . In particular, we show that the gr…
On algorithmic applications of sim-width and mim-width of -free graphs
Andrea Munaro, Shizhou Yang
Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While sev…
Solving Problems on Generalized Convex Graphs via Mim-Width
Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro +1
A bipartite graph is -convex, for some family of graphs , if there exists a graph with such that the set of neighbours in $…
List -Colouring -Free Graphs: a Mim-width Perspective
Nick Brettell, Jake Horsfield, Andrea Munaro +1
A colouring of a graph is a mapping such that for every two adjacent vertices and of . The {\sc List -Colourin…
Sublinear Longest Path Transversals
James A. Long, Kevin G. Milans, Andrea Munaro
We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of w…
Approximating Independent Set and Dominating Set on VPG graphs
Esther Galby, Andrea Munaro
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain -hard on -VPG graphs admi…
Bounding the Mim-Width of Hereditary Graph Classes
Nick Brettell, Jake Horsfield, Andrea Munaro +2
A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…
CPG graphs: Some structural and hardness results
Nicolas Champseix, Esther Galby, Andrea Munaro +1
In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a…
Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Esther Galby, Andrea Munaro, Bernard Ries
A semitotal dominating set of a graph with no isolated vertex is a dominating set of such that every vertex in is within distance two of another vertex in . The…
The VC-Dimension of Graphs with Respect to k-Connected Subgraphs
Andrea Munaro
We study the VC-dimension of the set system on the vertex set of some graph which is induced by the family of its -connected subgraphs. In particular, we give tight upper and lo…