23 citations · 60 across the 50 of their papers we have counts for
7 papers · 1 filter
A tight Erdős-Pósa function for wheel minors
Pierre Aboulker, Samuel Fiorini, Tony Huynh +3
Let denote the wheel on vertices. We prove that for every integer there is a constant such that for every integer and every graph , eit…
On the complexity of finding internally vertex-disjoint long directed paths
Júlio Araújo, Victor A. Campos, Ana Karolinna Maia +2
For two positive integers and , a -spindle is the union of pairwise internally vertex-disjoint directed paths with arcs between two vertices $…
On the (parameterized) complexity of recognizing well-covered (r,l)-graphs
Sancrey R. Alves, Konrad K. Dabrowski, Luerbio Faria +3
An -partition of a graph is a partition of its vertex set into independent sets and cliques. A graph is if it admits an -partition.…
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul +3
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirect…
Hitting minors on bounded treewidth graphs. I. General upper bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION problem consists in, given a graph and an integer , deciding whether there exists …
Ruling out FPT algorithms for Weighted Coloring on forests
Júlio Araújo, Julien Baste, Ignasi Sau
Given a graph , a proper -coloring of is a partition of into stable sets . Given a weight function $w: V(G) \to \ma…