research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
share
research
∙
09/16/2022
b-Coloring Parameterized by Pathwidth is XNLP-complete
We show that the b-Coloring problem is complete for the class XNLP when ...
research
∙
07/15/2022
A tight quasi-polynomial bound for Global Label Min-Cut
We study a generalization of the classic Global Min-Cut problem, called ...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
research
∙
02/07/2022
Reducing the Vertex Cover Number via Edge Contractions
The CONTRACTION(vc) problem takes as input a graph G on n vertices and t...
research
∙
07/08/2021
Using edge contractions to reduce the semitotal domination number
In this paper, we consider the problem of reducing the semitotal dominat...
research
∙
10/12/2020
Graph Square Roots of Small Distance from Degree One Graphs
Given a graph class ℋ, the task of the ℋ-Square Root problem is to decid...
research
∙
05/10/2020
Structural Parameterizations of Clique Coloring
A clique coloring of a graph is an assignment of colors to its vertices ...
research
∙
05/04/2020
Reducing graph transversals via edge contractions
For a graph parameter π, the Contraction(π) problem consists in, given a...
research
∙
03/09/2020
b-Coloring Parameterized by Clique-Width
We provide a polynomial-time algorithm for b-Coloring on graphs of const...
research
∙
03/06/2020
Algorithms for the rainbow vertex coloring problem on graph classes
Given a vertex-colored graph, we say a path is a rainbow vertex path if ...
research
∙
02/25/2020
Well-partitioned chordal graphs: obstruction set and disjoint paths
We introduce a new subclass of chordal graphs that generalizes split gra...
research
∙
06/28/2019
Blocking dominating sets for H-free graphs via edge contractions
In this paper, we consider the following problem: given a connected grap...
research
∙
03/05/2019
Reducing the domination number of graphs via edge contractions
In this paper, we study the following problem: given a connected graph G...
research
∙
01/07/2019
On the Parameterized Complexity of k-Edge Colouring
For every fixed integer k ≥ 1, we prove that k-Edge Colouring is fixed-p...
research
∙
11/09/2018
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
A b-coloring of a graph G is a proper coloring of its vertices such that...
research
∙
10/10/2018
Classifying k-Edge Colouring for H-free Graphs
A graph is H-free if it does not contain an induced subgraph isomorphic ...
research
∙
02/28/2018
Parameterized Aspects of Strong Subgraph Closure
Motivated by the role of triadic closures in social networks, and the im...
research
∙
12/19/2017