Daniël Paulusma

activity

20122025

most citedNarrowing the Complexity Gap for Colouring (

C_{s}

P_{t}

)-Free Graphs

8 citations · 14 across the 10 of their papers we have counts for

collaborators

Showing 2014Show all

4 papers · 1 filter

cs.DM2014★ 3 cited

Editing to Eulerian Graphs

Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +1

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let $e a$ , $e d$ and $v d$ denote t…

cs.CC2014★ 8 cited

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs

Shenwei Huang, Matthew Johnson, Daniël Paulusma

For a positive integer $k$ and graph $G = (V, E)$ , a $k$ -colouring of $G$ is a mapping $c : V \to {1, 2, \dots, k}$ such that $c (u) \neq = c (v)$ whenever $uv \in E$ . The $k$ -Colourin…

cs.DM2014★ 1 cited

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

Konrad K. Dabrowski, Daniël Paulusma

If a graph has no induced subgraph isomorphic to any graph in a finite family ${H_{1}, \dots, H_{p}}$ , it is said to be $(H_{1}, \dots, H_{p})$ -free. The class of $H$ -free graphs has bound…

cs.DS2014

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,..…

Editing to Eulerian Graphs

Narrowing the Complexity Gap for Colouring (Cs​,Pt​)-Free Graphs

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs