
Computing Balanced Solutions for Large International Kidney Exchange Schemes
To overcome incompatibility issues, kidney patients may swap their donor...
read it

Disjoint Paths and Connected Subgraphs for HFree Graphs
The wellknown Disjoint Paths problem is to decide if a graph contains k...
read it

Partitioning HFree Graphs of Bounded Diameter
A natural way of increasing our understanding of NPcomplete graph probl...
read it

Feedback Vertex Set and Even Cycle Transversal for HFree Graphs: Finding Large Block Graphs
We prove new complexity results for Feedback Vertex Set and Even Cycle T...
read it

Acyclic, Star, and Injective Colouring: Bounding the Diameter
We examine the effect of bounding the diameter for wellstudied variants...
read it

QCSP on Reflexive Tournaments
We give a complexity dichotomy for the Quantified Constraint Satisfactio...
read it

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
For k≥ 1, a kcolouring c of G is a mapping from V(G) to {1,2,…,k} such ...
read it

Induced Disjoint Paths in ATfree Graphs
Paths P_1,…,P_k in a graph G=(V,E) are mutually induced if any two disti...
read it

Hard Problems That Quickly Become Very Easy
A graph class is hereditary if it is closed under vertex deletion. We gi...
read it

The complexity of L(p,q)EdgeLabelling
We classify the complexity of L(p,q)EdgekLabelling in the sense that ...
read it

Acyclic, Star and Injective Colouring: A Complexity Picture for HFree Graphs
A kcolouring c of a graph G is a mapping V(G) to 1,2,... k such that c(...
read it

Solving problems on generalized convex graphs via mimwidth
A bipartite graph G=(A,B,E) is Hconvex, for some family of graphs H, if...
read it

List kColouring P_tFree Graphs with No Induced 1Subdivision of K_1,s: a Mimwidth Perspective
A colouring of a graph G=(V,E) is a mapping c V→{1,2,…} such that c(u)≠ ...
read it

Tree pivotminors and linear rankwidth
Treewidth and its linear variant pathwidth play a central role for the...
read it

Computing Weighted Subset Transversals in HFree Graphs
For the Odd Cycle Transversal problem, the task is to find a small set S...
read it

CliqueWidth: Harnessing the Power of Atoms
Many NPcomplete graph problems are polynomially solvable on graph class...
read it

Computing Subset Transversals in HFree Graphs
We study the computational complexity of two wellknown graph transversa...
read it

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
We consider the classical problems (Edge) Steiner Tree and Vertex Steine...
read it

Colouring (sP_1+P_5)Free Graphs: a MimWidth Perspective
We prove that the class of (K_t,sP_1+P_5)free graphs has bounded mimwi...
read it

Bounding the MimWidth of Hereditary Graph Classes
A large number of NPhard graph problems become polynomialtime solvable...
read it

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Let vc(G), fvs(G) and oct(G), respectively, denote the size of a minimum...
read it

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
A graph is Hfree if it contains no induced subgraph isomorphic to H. We...
read it

On the Parameterized Complexity of kEdge Colouring
For every fixed integer k ≥ 1, we prove that kEdge Colouring is fixedp...
read it

CliqueWidth for Hereditary Graph Classes
Cliquewidth is a wellstudied graph parameter owing to its use in under...
read it

Graph Isomorphism for (H_1,H_2)free Graphs: An Almost Complete Dichotomy
We consider the Graph Isomorphism problem for classes of graphs characte...
read it

Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
A simple game (N,v) is given by a set N of n players and a partition of ...
read it

Classifying kEdge Colouring for Hfree Graphs
A graph is Hfree if it does not contain an induced subgraph isomorphic ...
read it

Contracting to a Longest Path in HFree Graphs
We prove two dichotomy results for detecting long paths as patterns in a...
read it

Finding a Small Number of Colourful Components
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not nec...
read it

Colouring SquareFree Graphs without Long Induced Paths
The complexity of Colouring is fully understood for Hfree graphs, but ...
read it

Simple Games versus Weighted Voting Games
A simple game (N,v) is given by a set N of n players and a partition of ...
read it

Colouring (P_r+P_s)Free Graphs
The kColouring problem is to decide if the vertices of a graph can be c...
read it

Disconnected Cuts in Clawfree Graphs
A disconnected cut of a connected graph is a vertex cut that itself also...
read it

Connected Vertex Cover for (sP_1+P_5)Free Graphs
The Connected Vertex Cover problem is to decide if a graph G has a verte...
read it

On Colouring (2P_2,H)Free and (P_5,H)Free Graphs
The Colouring problem asks whether the vertices of a graph can be colour...
read it

Cliquewidth and WellQuasiOrdering of TriangleFree Graph Classes
Daligault, Rao and Thomassé asked whether every hereditary graph class t...
read it

Surjective HColouring over Reflexive Digraphs
The Surjective HColouring problem is to test if a given graph allows a ...
read it

Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity
We perform a systematic study in the computational complexity of the con...
read it

Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide
A graph is (H_1,H_2)free for a pair of graphs H_1,H_2 if it contains no...
read it

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
We consider a natural restriction of the List Colouring problem: kRegul...
read it

A Reconfigurations Analogue of Brooks' Theorem and its Consequences
Let G be a simple undirected graph on n vertices with maximum degree Δ. ...
read it

Finding Shortest Paths between Graph Colourings
The kcolouring reconfiguration problem asks whether, for a given graph ...
read it
Daniël Paulusma
is this you? claim profile
Professor in the Algorithms and Complexity research group (ACiD) at Durham University