D. Paulusma

activity

20092026

most citedSatisfiability of Acyclic and Almost Acyclic CNF Formulas

38 citations · 246 across the 68 of their papers we have counts for

collaborators

Showing math.COShow all

27 papers · 1 filter

math.CO2026

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen

The Chromatic Sum problem asks, given a graph $G$ and an integer $k$ , whether $G$ admits a colouring $c$ with sum $\sum_{v \in V} c (v) \leq k$ . We study the complexity of Chromatic S…

math.CO2026

On Detecting $H$ -Induced Minors for Small $H$

Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma +1

We consider the $H$ -Induced Minor problem: for a fixed graph~ $H$ , decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete fo…

math.CO2026

Optimal b-Colourings and Fall Colourings in $H$ -Free Graphs

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +3

In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight…

math.CO2026

Steiner Forest for $H$ -Subgraph-Free Graphs

Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4

Our main result is a full classification, for every connected graph $H$ , of the computational complexity of Steiner Forest on $H$ -subgraph-free graphs. To obtain this dichotomy, we…

math.CO2025

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Tala Eagling-Vose, Jorik Jooken, Felicia Lucke +2

We consider Colouring on graphs that are $H$ -subgraph-free for some fixed graph $H$ , which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring…

math.CO2025

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…

math.CO2025

Finding d-Cuts in Claw-free Graphs

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +2

The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets $B$ and $R$ such that the edges between $B$ and $R$ form a m…

math.CO2025

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs

Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1

We continue the study of the recently-introduced C123-framework, for (simple) graph problems restricted to inputs specified by the forbidding of some finite set of subgraphs, to mo…

math.CO2023

Computing pivot-minors

Konrad K. Dabrowski, François Dross, Jisu Jeong +4

A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in…

math.CO2023

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…

math.CO2023

Computing Subset Vertex Covers in $H$ -Free Graphs

Nick Brettell, Jelle J. Oostveen, Sukanya Pandey +3

We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph $G = (V, E)$ , a subset $T \subseteq V$ and integer $k$ , if $V$ has…

math.CO2022★ 1 cited

Complexity Framework For Forbidden Subgraphs I: The Framework

Matthew Johnson, Barnaby Martin, Jelle J. Oostveen +4

For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. T…

math.CO2022★ 1 cited

Finding Matching Cuts in $H$ -Free Graphs

Felicia Lucke, Daniël Paulusma, Bernard Ries

The NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to $H…

math.CO2022

Few Induced Disjoint Paths for $H$ -Free Graphs

Barnaby Martin, Daniël Paulusma, Siani Smith +1

Paths $P^{1}, \dots, P^{k}$ in a graph $G = (V, E)$ are mutually induced if any two distinct $P^{i}$ and $P^{j}$ have neither common vertices nor adjacent vertices. For a fixed integer $k$ , th…

math.CO2022

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs

Barnaby Martin, Daniël Paulusma, Siani Smith +1

Paths $P_{1}, \dots, P_{k}$ in a graph $G = (V, E)$ are mutually induced if any two distinct $P_{i}$ and $P_{j}$ have neither common vertices nor adjacent vertices. The Induced Disjoint Paths…

math.CO2021

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Walter Kern, Barnaby Martin, Daniël Paulusma +2

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We deter…

math.CO2021

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

Barnaby Martin, Daniel Paulusma, Siani Smith

For $k \geq 1$ , a $k$ -colouring $c$ of $G$ is a mapping from $V (G)$ to ${1, 2, \dots, k}$ such that $c (u) \neq = c (v)$ for any two non-adjacent vertices $u$ and $v$ . The $k$ -Colouring…

math.CO2020

Tree pivot-minors and linear rank-width

Konrad K. Dabrowski, François Dross, Jisu Jeong +4

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~ $T$ , the class…

math.CO2019★ 1 cited

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2

Let $v c (G)$ , $f v s (G)$ and $oc t (G)$ , respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph $G$ . One can a…

math.CO2019★ 25 cited

Clique-Width for Hereditary Graph Classes

Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class $G$ is bounded by a constant,…

math.CO2018

Colouring Square-Free Graphs without Long Induced Paths

Serge Gaspers, Shenwei Huang, Daniël Paulusma

The complexity of {\sc Colouring} is fully understood for $H$ -free graphs, but there are still major complexity gaps if two induced subgraphs $H_{1}$ and $H_{2}$ are forbidden. Let $H_…

math.CO2017

Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes

Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma

Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamar…

math.CO2016

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev rece…

math.CO2016★ 2 cited

New Bounds for the Snake-in-the-Box Problem

David Allison, Daniel Paulusma

The Snake-in-the-Box problem is that of finding a longest induced path in an $n$ -dimensional hypercube. We prove new lower bounds for the values $n \in {11, 12, 13}$ . The Coil-in-th…

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

On Detecting H-Induced Minors for Small H

Optimal b-Colourings and Fall Colourings in H-Free Graphs

Steiner Forest for H-Subgraph-Free Graphs

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Graph Classes Closed under Self-intersection

Finding d-Cuts in Claw-free Graphs

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs

Computing pivot-minors

Comparing Width Parameters on Graph Classes

Computing Subset Vertex Covers in H-Free Graphs

Complexity Framework For Forbidden Subgraphs I: The Framework

Finding Matching Cuts in H-Free Graphs

Few Induced Disjoint Paths for H-Free Graphs

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

Tree pivot-minors and linear rank-width

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Clique-Width for Hereditary Graph Classes

Colouring Square-Free Graphs without Long Induced Paths

Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

New Bounds for the Snake-in-the-Box Problem

On Detecting $H$ -Induced Minors for Small $H$

Optimal b-Colourings and Fall Colourings in $H$ -Free Graphs

Steiner Forest for $H$ -Subgraph-Free Graphs

Computing Subset Vertex Covers in $H$ -Free Graphs

Finding Matching Cuts in $H$ -Free Graphs

Few Induced Disjoint Paths for $H$ -Free Graphs

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs