Papers
See also my profiles on Google Scholar and
dblp.
For preprints see
here.
Theses
 D. Paulusma, Complexity Aspects of Cooperative Games, PhD Thesis, University of Twente, Enschede,
the Netherlands, 2001.
 D. Paulusma, Extensions of the Shapley Value for TUGames Defined on Posets, Master Thesis,
University of Twente, Enschede, the Netherlands, 1997.
Journal Publications

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,
Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, to appear in Journal of Graph Theory.
 H. Bodlaender, N. Brettell, M. Johnson, G. Paesani, D. Paulusma and E.J. van Leeuwen, Steiner trees for hereditary graph classes: a treewidth perspective,
Theoretical Computer Science
867 (2021) 3039
doi.

M. Bonamy, N. Bousquet, K.K. Dabrowski, M. Johnson, D. Paulusma and T. Pierron, Graph isomorphism for (H1,H2)free graphs: an almost complete dichotomy,
Algorithmica 83 (2021) 822852
doi.

A. Blanche, K.K. Dabrowski, M. Johnson, V.V. Lozin, D. Paulusma and V. Zamaraev,
Cliquewidth for graph classes closed under complementation,
SIAM Journal on Discrete Mathematics 34 (2020) 11071147
doi.

K.K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma and P. Rzazewski,
On cycle transversals and their connected variants in the absence of a small linear forest,
Algorithmica 82 (2020) 28412866
doi.

K.K. Dabrowski, V.V. Lozin and D. Paulusma,
Cliquewidth and wellquasi ordering of trianglefree graph classes,
Journal of Computer and System Sciences
108 (2020) 6491
doi.

F. Hof, W. Kern, S. Kurz, K. Pashkovich and D. Paulusma, Simple games versus weighted voting games:
bounding the critical threshold value, Social Choice and Welfare
54 (2020) 609621
doi.

M. Johnson, G. Paesani and D. Paulusma, Connected vertex cover for (sP1+P5)free graphs,
Algorithmica
82 (2020) 2040
doi.

T. Klimosova, J. Malik, T. Masarik, J. Novotna, D. Paulusma and V. Slivova, Colouring (Pr+Ps)free graphs,
Algorithmica 82 (2020) 18331858
doi.

B. Martin, D. Paulusma and E.J. van Leeuwen, Disconnected cuts in clawfree graphs,
Journal of Computer and System Sciences
113 (2020) 6075
doi.

A. Blanche, K.K. Dabrowski, M. Johnson and D. Paulusma, Hereditary graph classes: when the complexities of colouring and clique cover coincide, Journal of Graph Theory 91 (2019) 267289
doi.

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,
Independent feedback vertex set for P5free graphs, Algorithmica
81 (2019) 13421369
doi.

P. Bonsma and D. Paulusma, Using contracted solution graphs for solving reconfiguration problems,
Acta Informatica 56 (2019) 619648
doi.

K.K. Dabrowski, F. Dross, M. Johnson and D. Paulusma,
Filling the complexity gaps for colouring planar and bounded degree graphs,
Journal of Graph Theory 92 (2019) 377393
doi.

K.K. Dabrowski, S. Huang and D. Paulusma, Bounding cliquewidth via perfect graphs,
Journal of Computer and System Sciences
104 (2019) 202215
doi.

K.K. Dabrowski, M. Johnson and D. Paulusma,
Cliquewidth for hereditary graph classes,
London Mathematical Society Lecture Note Series 456 (2019) 156
doi.

E. Galby, P.T. Lima, D. Paulusma and B. Ries, Classifying kEdge Colouring for Hfree graphs,
Information Processing Letters 146 (2019) 3943
doi.

S. Gaspers, S. Huang and D. Paulusma, Colouring squarefree graphs without long induced paths,
Journal of Computer and System Sciences
106 (2019) 6079
doi.

P.A. Golovach, P. Heggernes, D. Kratsch, P.T. Lima and D. Paulusma,
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2,
Algorithmica 81 (2019) 27952828
doi.

P.A. Golovach, M. Johnson, B. Martin, D. Paulusma and A. Stewart,
Surjective HColouring: new hardness results,
Computability 8 (2019) 2742
doi.

B. Larose, B. Martin and D. Paulusma, Surjective HColouring over reflexive digraphs,
ACM Transactions on Computation Theory 11 (2019) 3:13:21
doi.

D. Paulusma, C. Picouleau and B. Ries,
Critical vertices and edges in Hfree graphs, Discrete Applied Mathematics 257 (2019) 361367
doi.

D. Paulusma and S. Szeider, On the parameterized complexity of (k,s)SAT, Information Processing Letters 143 (2019) 3436 doi.

P. Biro, W. Kern, D. Paulusma and P. Wojuteczky,
The stable fixtures problem with payments,
Games and Economic Behavior
108 (2018) 245268
doi.

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,
Independent feedback vertex sets for graphs of bounded diameter, Information Processing Letters 131 (2018) 2632
doi.

N. Chiarelli, T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma,
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity,
Theoretical Computer Science 705 (2018) 7583
doi.

M. Cochefert, J.F. Couturier, P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Computing square roots of graphs with low maximum degree,
Discrete Applied Mathematics 248 (2018) 93101
doi.

K.K. Dabrowski, V. Lozin and D. Paulusma,
Wellquasiordering versus cliquewidth: new results on bigenic classes,
Order 35 (2018) 253274
doi.

K.K. Dabrowski and D. Paulusma,
On colouring (2P2,H)free and (P5,H)free graphs,
Information Processing Letters 134 (2018) 3541
doi.

O. Diner, D. Paulusma, C. Picouleau and B. Ries,
Contraction and deletion blockers for perfect graphs and Hfree graphs, Theoretical Computer Science 746 (2018)
4972
doi.

P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Finding cactus roots in polynomial time,
Theory of Computing Systems 62 (2018) 14091426
doi.

A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma, Bounding the cliquewidth of Hfree chordal graphs,
Journal of Graph Theory 86 (2017) 4277
doi.

R. Belmonte, P. van 't Hof, M. Kaminski and D. Paulusma,
The price of connectivity for feedback vertex set,
Discrete Applied Mathematics 217 (2017) 132143
doi.

K.K. Dabrowski, F. Dross and D. Paulusma,
Colouring diamondfree graphs,
Journal of Computer and System Sciences
89 (2017) 410431
doi.

K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos,
Editing to a planar graph of given degrees,
Journal of Computer and System Sciences 85 (2017) 168182
doi.

K.K. Dabrowski and D. Paulusma,
Contracting bipartite graphs to paths and cycles,
Information Processing Letters
127 (2017) 3742
doi.

C. Feghali, M. Johnson and D. Paulusma,
Kempe equivalence of colourings of cubic graphs,
European Journal of Combinatorics 59 (2017) 110
doi.

P.A. Golovach, M. Johnson, D. Paulusma and J. Song,
A survey on the computational complexity of colouring graphs with forbidden subgraphs,
Journal of Graph Theory 84 (2017) 331363
doi.

P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
A linear kernel for finding square roots of almost planar graphs,
Theoretical Computer Science 689 (2017) 3647
doi.

P.A. Golovach, D. Paulusma and I.A. Stewart,
Graph editing to a fixed target,
Discrete Applied Mathematics
216 (2017) 181190
doi.

A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma,
Bounding the cliquewidth of Hfree split graphs,
Discrete Applied Mathematics 211 (2016) 3039
doi.

M. Cochefert, J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma,
Parameterized algorithms for finding square roots, Algorithmica
74 (2016) 602629
doi.

K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma, Editing to Eulerian graphs, Journal of Computer and System Sciences
82 (2016) 213228
doi.

K.K. Dabrowski and D. Paulusma,
Classifying the cliquewidth of Hfree bipartite graphs,
Discrete Applied Mathematics 200 (2016) 4351
doi.

K.K. Dabrowski and D. Paulusma,
Cliquewidth of graph classes defined by two forbidden induced subgraphs,
The Computer Journal 59 (2016) 650666
doi.

C. Feghali, M. Johnson and D. Paulusma,
A reconfigurations analogue of Brooks' Theorem and its consequences,
Journal of Graph Theory 83 (2016) 340358
doi.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen,
Induced disjoint paths in circulararc graphs in linear time,
Theoretical Computer Science 640 (2016) 7083
doi.

T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma,
The price of connectivity for cycle transversals,
European Journal of Combinatorics 58 (2016) 203224
doi.

M. Johnson, D. Kratsch, S. Kratsch, V. Patel and D. Paulusma,
Finding shortest paths between graph colourings,
Algorithmica 75 (2016) 295321
doi.

M. Kaminski, D. Paulusma, A. Stewart and D.M. Thilikos,
Minimal disconnected cuts in planar graphs,
Networks 68 (2016) 250259
doi.

D. Paulusma, F. Slivovsky and S. Szeider,
Model counting for CNF formulas of bounded modular treewidth,
Algorithmica
76 (2016) 168194
doi.

H.J. Broersma, J. Fiala, P.A. Golovach, T. Kaiser, D. Paulusma and A. Proskurowski,
Lineartime algorithms for scattering number and hamiltonconnectivity of interval graphs, Journal of Graph Theory
79 (2015) 282299.
doi.

S. Chaplick, J. Fiala, P. van 't Hof, D. Paulusma and M. Tesar,
Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree, Theoretical Computer Science
590 (2015) 8695
doi.

J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma,
List coloring in the absence of a linear forest,
Algorithmica 71 (2015) 2135
doi.

P.A. Golovach, P. Heggernes, P. van 't Hof, F. Manne, D. Paulusma and M. Pilipczuk,
Modifying a graph using vertex elimination,
Algorithmica 72 (2015) 99125
doi.

P.A. Golovach, D. Paulusma and B. Ries,
Coloring graphs characterized by a forbidden subgraph,
Discrete Applied Mathematics 180 (2015) 101110
doi.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen, Induced disjoint paths in clawfree graphs,
SIAM Journal on Discrete Mathematics 29 (2015) 348375
doi.

S. Huang, M. Johnson and D. Paulusma,
Narrowing the complexity gap for colouring (Cs,Pt)free graphs,
The Computer Journal 58 (2015) 30743088
doi.

M. Johnson, D. Paulusma and A. Stewart,
Knocking out Pkfree graphs,
Discrete Applied Mathematics
190 (2015) 100108
doi.

M. Johnson, D. Paulusma and E.J. van Leeuwen,
Algorithms to measure diversity and clustering in social networks through dot product graphs,
Social Networks 41 (2015) 4855
doi.

B. Martin and D. Paulusma,
The computational complexity of Disconnected Cut and 2K2Partition,
Journal of Combinatorial Theory, Series B
111 (2015) 1737
doi.

R. Belmonte, P.A. Golovach, P. Heggernes, P. van 't Hof, M. Kaminski and D. Paulusma,
Detecting fixed patterns in chordal graphs in polynomial time,
Algorithmica 69 (2014) 501521
doi.

R. Belmonte, P.A. Golovach, P. van 't Hof and D. Paulusma,
Parameterized complexity of three edge contraction problems with degree constraints, Acta Informatica 51 (2014) 473497
doi.

P. Biro, M. Bomhoff, P.A. Golovach, W. Kern and D. Paulusma,
Solutions for the stable roommates problem with payments,
Theoretical Computer Science 540 (2014) 5361
doi.

M. Bonamy, M. Johnson, I.M. Lignos, V. Patel and D. Paulusma,
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs,
Journal of Combinatorial Optimization 27 (2014) 132143
doi.

J. Chalopin and D. Paulusma, Packing bipartite graphs with covers of complete bipartite graphs,
Discrete Applied Mathematics 168 (2014) 4050
doi.

K.K. Dabrowski, P.A. Golovach and D. Paulusma,
Colouring of graphs with Ramseytype forbidden subgraphs, Theoretical Computer Science 522 (2014) 3443
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Liftcontractions,
European Journal of Combinatorics
35 (2014) 286296
doi.

P.A. Golovach and D. Paulusma,
List coloring in the absence of two subgraphs,
Discrete Applied Mathematics 166 (2014) 123130
doi.

P.A. Golovach, D. Paulusma and J. Song,
Closing complexity gaps for coloring problems on Hfree graphs,
Information and Computation 237 (2014) 204214
doi.

P.A. Golovach, D. Paulusma and J. Song,
Coloring graphs without short cycles and long induced paths,
Discrete Applied Mathematics 167 (2014) 107120
doi.

M. Johnson, V. Patel, D. Paulusma and T. Trunck,
Obtaining online ecological colourings by generalizing firstfit,
Theory of Computing Systems 54 (2014) 244260
doi.

R. Belmonte, P. van 't Hof, M. Kaminski, D. Paulusma and D.M. Thilikos,
Characterizing graphs of small carvingwidth, Discrete Applied Mathematics 161 (2013) 18881893
doi.

H.J. Broersma, F.V. Fomin, P.A. Golovach and D. Paulusma,
Three complexity results on coloring Pkfree graphs,
European Journal of Combinatorics 34 (2013) 609619
doi.
 H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma,
Exact algorithms for finding longest cycles in clawfree graphs,
Algorithmica
65 (2013) 129145
doi.

J. Fiala, M. Kaminski and D. Paulusma,
A note on contracting clawfree graphs,
Discrete Mathematics & Theoretical Computer Science
15 (2013) 223232
doi.

P.A. Golovach, P. Heggernes, P. van 't Hof and D. Paulusma,
Choosability on Hfree graphs,
Information Processing Letters
113 (2013) 107110
doi.

P.A. Golovach, P. van 't Hof and D. Paulusma,
Obtaining planarity by contracting few edges,
Theoretical Computer Science 476 (2013) 3846
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Increasing the minimum degree of a graph by contractions,
Theoretical Computer Science
481 (2013) 7484
doi.

P.A. Golovach, D. Kratsch and D. Paulusma,
Detecting induced minors in ATfree graphs,
Theoretical Computer Science 482 (2013) 2032
doi.

P.A. Golovach, D. Paulusma and J. Song,
4Coloring Hfree graphs when H is small,
Discrete Applied Mathematics 161 (2013) 140150
doi.

S. Ordyniak, D. Paulusma and S. Szeider,
Satisfiability of acyclic and almost acyclic CNF formulas,
Theoretical Computer Science
481 (2013) 8599
doi.

P. Biro, W. Kern and D. Paulusma, Computing solutions for matching games, International Journal of Game Theory
41 (2012) 7590
doi.
 H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song,
Determining the chromatic number of trianglefree 2P3free graphs in polynomial time,
Theoretical Computer Science 423 (2012) 110
doi.
 H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song,
Updating the complexity status of coloring graphs without a fixed induced linear forest,
Theoretical Computer Science 414 (2012) 919
doi.

J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma,
On the parameterized complexity of coloring graphs in the absence of a linear forest, Journal of Discrete Algorithms
15 (2012) 5662
doi.
 J. Fiala, P.A. Golovach, J. Kratochvil, B. Lidicky and D. Paulusma,
Distance three labelings of trees, Discrete Applied Mathematics 160 (2012) 764779
doi.
 J. Fiala, M. Kaminski, B. Lidicky and D. Paulusma,
The kinapath problem for clawfree graphs, Algorithmica 62 (2012) 499519
doi.

J. Fiala, M. Kaminski and D. Paulusma,
Detecting induced starlike minors in polynomial time, Journal of Discrete Algorithms 17 (2012) 7485
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Containment relations in split graphs, Discrete Applied Mathematics 160 (2012) 155163
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Induced packing of odd cycles in planar graphs, Theoretical Computer Science 420 (2012) 2835
doi.

P.A. Golovach, B. Lidicky, B. Martin and D. Paulusma,
Finding vertexsurjective graph homomorphisms,
Acta Informatica 49 (2012) 381394
doi.

P.A. Golovach, D. Paulusma and J. Song,
Computing vertexsurjective homomorphisms to partially reflexive trees,
Theoretical Computer Science 457 (2012) 86100
doi.

P. Heggernes, P. van 't Hof and D. Paulusma,
Computing role assignments of proper interval graphs in polynomial time, Journal of Discrete Algorithms
14 (2012) 173188
doi.

P. van 't Hof, M. Kaminski and D. Paulusma,
Finding induced paths of given parity in clawfree graphs, Algorithmica 62 (2012) 537563
doi.

P. van 't Hof, M. Kaminski, D. Paulusma, S. Szeider and D.M. Thilikos,
On graph contractions and induced minors, Discrete Applied Mathematics 160 (2012) 799809
doi.
 J. Chalopin and D. Paulusma, Graph labelings derived from models in
distributed computing: a complete complexity classification,
Networks 58 (2011) 207231
doi.

T. Ito, M. Kaminski, D. Paulusma and D.M. Thilikos,
Parameterizing cut sets in a graph by the number of their components,
Theoretical Computer Science 412 (2011) 63406350
doi.

T. Ito, M. Kaminski, D. Paulusma and D.M. Thilikos,
On disconnected cuts and separators, Discrete Applied
Mathematics 159 (2011) 13451351
doi.

M. Kaminski, D. Paulusma and D.M. Thilikos,
Contracting planar graphs to contractions of triangulations,
Journal of Discrete Algorithms 9 (2011) 299306
doi.

D. Paulusma and J.M.M. van Rooij,
On partitioning a graph into two connected subgraphs,
Theoretical Computer Science 412 (2011) 67616769
doi.
 H.J. Broersma and D. Paulusma,
Computing sharp 2factors in clawfree graphs, Journal of Discrete Algorithms 8 (2010) 321329
doi.
 J. Fiala and D. Paulusma, Comparing universal covers in polynomial time, Theory of Computing Systems 46 (2010) 620635
doi.
 P. van 't Hof and D. Paulusma,
A new characterization of P6free graphs,
Discrete Applied Mathematics 158 (2010) 731740
doi.

P. van 't Hof, D. Paulusma and J.M.M. van Rooij,
Computing role assignments of chordal graphs, Theoretical
Computer Science 411 (2010) 36013613
doi.

M. Johnson, D. Paulusma and C. Wood,
Path factors and parallel knockout schemes of almost clawfree graphs,
Discrete Mathematics 310 (2010) 14131423
doi.

H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto,
lBackbone colorings along pairwise disjoint stars and matchings,
Discrete Mathematics 309 (2009) 55965609
doi.

H.J. Broersma, M. Johnson and D. Paulusma,
Upper bounds and algorithms for parallel knockout numbers,
Theoretical Computer Science 410 (2009) 13191327
doi.
 H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman,
Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number,
Discussiones Mathematicae Graph Theory 29 (2009) 143162
doi.
 H.J. Broersma, D. Paulusma and K. Yoshimoto,
Sharp upper bounds for the minimum number of components of
2factors in clawfree graphs, Graphs and Combinatorics
25 (2009) 427460
doi.

H. Fleischner, E. Mujuni, D. Paulusma and S. Szeider,
Covering graphs with few complete bipartite subgraphs,
Theoretical Computer Science 410 (2009) 20452053
doi.
 P. van 't Hof, D. Paulusma and G.J. Woeginger,
Partitioning graphs into connected parts,
Theoretical Computer Science 410 (2009) 48344843
doi.

W. Kern and D. Paulusma, On the core and fnucleolus of flow games,
Mathematics of Operations Research 34 (2009) 981991
doi.

H.J. Broersma, A. Capponi and D. Paulusma,
A new algorithm for online coloring bipartite graphs,
SIAM Journal on Discrete Mathematics 22 (2008) 7291
doi.

H.J. Broersma, M. Johnson, D. Paulusma and I.A. Stewart,
The computational complexity of the parallel knockout problem,
Theoretical Computer Science 393 (2008) 182195
doi.

J. Fiala, D. Paulusma and J.A. Telle, Locally constrained graph homomorphisms and equitable partitions, European Journal of Combinatorics 29 (2008) 850880
doi.
 A. Levin, D. Paulusma and G.J. Woeginger,
The computational complexity of graph contractions II: two tough polynomially solvable cases,
Networks 52 (2008) 3256
doi.
 A. Levin, D. Paulusma and G.J. Woeginger,
The computational complexity of graph contractions I: polynomially solvable and NPcomplete cases,
Networks 51 (2008) 178189
doi.
 D. Paulusma and K. Yoshimoto, Relative length of longest paths and
longest cycles in trianglefree graphs, Discrete Mathematics 308 (2008) 12221229
doi.
 D. Paulusma and K. Yoshimoto, Cycles through specified vertices in trianglefree graphs,
Discussiones Mathematicae Graph Theory 27 (2007) 179191
doi.
 J. Fiala and D. Paulusma, A complete complexity classification of the role assignment problem,
Theoretical Computer Science 349 (2005) 6781
doi.
 W. Kern and D. Paulusma, The computational complexity of the elimination problem in generalized sports competitions, Discrete Optimization
1 (2004) 205214
doi.
 W. Kern and D. Paulusma, Matching games: the least core and the nucleolus,
Mathematics of Operations Research 28 (2003) 294308
doi.
 T.S.H. Driessen and D. Paulusma, Two extensions of the Shapley value for cooperative games,
Mathematical Methods of Operations Research 53 (2001) 3549
doi.
 W. Kern and D. Paulusma, The new FIFA rules are hard: complexity aspects of sport competitions, Discrete Applied Mathematics 108 (2001) 317323
doi.
 U. Faigle, W. Kern and D. Paulusma, Note on the computational complexity of least core concepts for mincost spanning tree games, Mathematical Methods of Operations Research 52 (2000) 2338
doi.
Publications in Conference Proceedings

C. Brause, P.A. Golovach, B. Martin, D. Paulusma and S. Smith, Acyclic, star and injective colouring: bounding the diameter, Proceedings of the 47th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2021), Warsaw, Poland, June 2325, 2021, Lecture Notes in Computer Science, to appear.
 F. BonomoBraberman, N. Brettell, A. Munaro and D. Paulusma, Solving problems on generalized convex graphs via mimwidth, Proceedings of the 17th Algorithms and Data Structures Symposium (WADS 2021),
Halifax, Nova Scotia, Canada, August 911, 2021, Lecture Notes in Computer Science, to appear.
 N. Brettell, M. Johnson and D. Paulusma, Computing weighted subset transversals in Hfree graphs, Proceedings of the 17th Algorithms and Data Structures Symposium (WADS 2021),
Halifax, Nova Scotia, Canada, August 911, 2021, Lecture Notes in Computer Science, to appear.

J. Bok, N. Jedlickova, B. Martin, D. Paulusma and S. Smith, Injective colouring for Hfree graphs, Proceedings of the 16th International Computer Science Symposium in Russia (CSR 2021),
Sochi, Russia, June 28July 2, 2021, Sochi, Russia, Lecture Notes in Computer Science, to appear.

W. Kern, B. Martin, D. Paulusma, S. Smith and E.J. van Leeuwen, Disjoint paths and connected subgraphs for Hfree graphs,
Proceedings of the 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), Ottawa, Canada, July 58, 2021, Lecture Notes in Computer Science, to appear.

B. Martin, D. Paulusma and S. Smith, Colouring graphs of bounded diameter in the absence of small cycles, Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021),
Larnaca, Cyprus, May 1012, 2021, Lecture Notes in Computer Science 12701, 367380
doi.

N. Brettell, J. Horsfield, A. Munaro, G. Paesani and D. Paulusma,
Bounding the mimwidth of hereditary graph classes,
Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Hong Kong, China, December 1418, 2020,
Leibniz International Proceedings in Informatics 180, 6:16:18
doi.

W. Kern and D. Paulusma, Contracting to a longest path in Hfree graphs,
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020),
Hong Kong, China, December 1418, 2020,
Leibniz International Proceedings in Informatics 181, 22:122:18
doi.

N. Brettell, M. Johnson, G. Paesani and D. Paulusma, Computing subset transversals in Hfree graphs,
Proceedings of the 46th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2020),
Leeds, UK, June 2426, 2020, Lecture Notes in Computer Science 12301, 187199
doi.

K.K. Dabrowski, T. Masarik, J. Novotna, D. Paulusma and P. Rzazewski,
Cliquewidth: harnessing the power of atoms,
Proceedings of the 46th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2020),
Leeds, UK, June 2426, 2020, Lecture Notes in Computer Science 12301, 119133
doi.
 H. Bodlaender, N. Brettell, M. Johnson, G. Paesani, D. Paulusma and E.J. van Leeuwen, Steiner trees for hereditary graph classes, Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN 2020), Lecture Notes in Computer Science 12118, 613624
doi.

J. Bok, N. Jedlickova, B. Martin, D. Paulusma and S. Smith, Acyclic, star and injective colouring: a complexity picture for Hfree graphs, Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020),
Pisa, Italy, September 79, 2020, Leibniz International Proceedings in Informatics 173, 22:122:22
doi.

K.K. Dabrowski, F. Dross, J. Jeong, M.M. Kante, O. Kwon, S. Oum and D. Paulusma, Tree pivotminors and linear rankwidth,
Proceedings of the 10th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Bratislava, Slovakia, August 2630, 2019, Acta Mathematica Universitatis Comenianae 88, 585591
doi.

K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev, Independent transversals versus transversals,
Proceedings of the 10th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Bratislava, Slovakia, August 2630, 2019, Acta Mathematica Universitatis Comenianae 88, 577583
doi.

B. Martin, D. Paulusma and S. Smith, Colouring Hfree graphs of bounded diameter, Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019),
Aachen, Germany, August 2630, 2019, Leibniz International Proceedings in Informatics 138, 14:114:14
doi

C. Feghali, M. Johnson, G. Paesani and D. Paulusma,
On cycle transversals and their connected variants in the absence of a small linear forest,
Proceedings of the 22th International Symposium on Fundamentals of Computation Theory (FCT 2019), Copenhagen, Denmark, August 1114, 2019, Lecture Notes in Computer Science 11651, 258273,
doi.

M. Bonamy, K.K. Dabrowski, M. Johnson and D. Paulusma, Graph isomorphism for (H1,H2)free graphs: an almost complete dichotomy,
Proceedings of the 16th Algorithms and Data Structures Symposium
(WADS 2019), Edmonton, Canada, August 57, 2019, Lecture Notes in Computer Science 11646, 181195,
doi.

P. Biro, W. Kern, D. Palvolgyi and D. Paulusma,
Generalized matching games for international kidney exchange,
Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems
(AAMAS 2019), 413421, Montreal, Canada, May 1317, 2019
doi.

L. Bulteau, K.K. Dabrowski, G. Fertin, M. Johnson, D. Paulusma and S. Vialette,
Finding a small number of colourful components,
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching
(CPM 2019), Pisa, Italy, June 1820, 2019, Leibniz International Proceedings in Informatics 128, 20:120:14
doi.

T. Klimosova, J. Malik, T. Masarik, J. Novotna, D. Paulusma and V. Slivova, Colouring (Pr+Ps)free graphs,
Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018),
Jiaoxi, Taiwan, December 1619, 2018,
Leibniz International Proceedings in Informatics 123, 5:15:13
doi.

K.K. Dabrowski, F. Dross, J. Jeong, M.M. Kante, O. Kwon, S. Oum and D. Paulusma, Computing small pivotminors,
Proceedings of the 44th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2018),
Cottbus, Germany, June 2729, 2018, Lecture Notes in Computer Science 11159, 125138,
doi.

M. Johnson, G. Paesani and D. Paulusma, Connected vertex cover for (sP1+P5)free graphs,
Proceedings of the 44th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2018),
Cottbus, Germany, June 2729, 2018, Lecture Notes in Computer Science 11159, 279291
doi.

F. Hof, W. Kern, S. Kurz and D. Paulusma, Simple games versus weighted voting games,
Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT 2018), Beijing, China, September 1113, 2018, Lecture Notes in Computer Science 11059, 6981
doi.

K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev,
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal,
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018),
Liverpool, UK, August 2731, 2018, Leibniz International Proceedings in Informatics 117, 63:163:15
doi.

B. Martin, D. Paulusma and E.J. van Leeuwen, Disconnected cuts in clawfree graphs,
Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018),
Helsinki, Finland, August 2022, 2018,
Leibniz International Proceedings in Informatics 112, 61:161:14
doi.

S. Gaspers, S. Huang and D. Paulusma, Colouring squarefree graphs without long induced paths,
Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018),
Caen, France, February 28  March 3, 2018,
Leibniz International Proceedings in Informatics 96, 35:135:15
doi.

B. Larose, B. Martin and D. Paulusma, Surjective HColouring over reflexive digraphs,
Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018),
Caen, France, February 28  March 3, 2018,
Leibniz International Proceedings in Informatics 96, 49:149:14
doi.

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,
Independent feedback vertex set for P5free graphs,
Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017),
Phuket, Thailand, December 912, 2017,
Leibniz International Proceedings in Informatics 92, 16:116.12
doi.

A. Blanche, K.K. Dabrowski, M. Johnson, V.V. Lozin, D. Paulusma and V. Zamaraev,
Cliquewidth for graph classes closed under complementation,
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017),
Aalborg, Denmark, August 2125, 2017,
Leibniz International Proceedings in Informatics 83, 73:173:14
doi.

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,
Recognizing graphs close to bipartite graphs,
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017),
Aalborg, Denmark, August 2125, 2017,
Leibniz International Proceedings in Informatics 83, 70:170:14
doi.

K.K. Dabrowski, V.V. Lozin and D. Paulusma,
Cliquewidth and wellquasi ordering of trianglefree graph classes,
Proceedings of the 43rd International Workshop on GraphTheoretic Concepts in Computer Science (WG 2017),
Eindhoven, the Netherlands, June 2123, 2017,
Lecture Notes in Computer Science 10520, 220233
doi.

P.A. Golovach, P. Heggernes, D. Kratsch, P.T. Lima and D. Paulusma,
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2,
Proceedings of the 43rd International Workshop on GraphTheoretic Concepts in Computer Science (WG 2017),
Eindhoven, the Netherlands, June 2123, 2017,
Lecture Notes in Computer Science 10520, 275288
doi.

D. Paulusma, C. Picouleau and B. Ries,
Reducing the chromatic number by vertex or edge deletions,
Proceedings of the 9th Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2017),
Marseille, France, September 1115, 2017,
Electronic Notes in Discrete Mathematics 62, 243248
doi.

K.K. Dabrowski and D. Paulusma,
Contracting bipartite graphs to paths and cycles,
Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Vienna, Austria, August 28  September 1, 2017,
Electronic Notes in Discrete Mathematics 61, 309315
doi.

P.A. Golovach, M. Johnson, B. Martin, D. Paulusma and A. Stewart,
Surjective HColouring: new hardness results,
Proceedings of the 13th Conference on Computability in Europe (CiE 2017), Turku, Finaland, June 1216, Lecture Notes in Computer Science 10307, 270281
doi.

D. Paulusma, C. Picouleau and B. Ries, Blocking independent sets for Hfree graphs via edge contractions and vertex deletions,
Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation (TAMC 2017), Bern, Switzerland, April 2022, 2017, Lecture Notes in Computer Science 10185, 470483
doi.

D. Paulusma, C. Picouleau and B. Ries,
Reducing the clique and chromatic number via edge contractions and vertex deletions,
Proceedings of the 4th International Symposium on Combinatorial Optimization (ISCO 2016),
Vietri sul Mare, Salerno, Italy, May 1618, 2016,
Lecture Notes in Computer Science 9849, 3849
doi.

P. Bonsma and D. Paulusma, Using contracted solution graphs for solving reconfiguration problems,
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science
(MFCS 2016), Krakow, Poland, August 2226, 2016, Leibniz International Proceedings in Informatics 58, 20:120:15
doi.

K.K. Dabrowski, V. Lozin and D. Paulusma,
Wellquasiordering versus cliquewidth: new results on bigenic classes,
Proceedings of the 27th International Workshop on Combinatorial Algorithms
(IWOCA 2016), Helsinki, Finland, August 1719, 2016, Lecture Notes in Computer Science 9843, 253265
doi.

P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Finding cactus roots in polynomial time,
Proceedings of the 27th International Workshop on Combinatorial Algorithms
(IWOCA 2016), Helsinki, Finland, August 1719, 2016, Lecture Notes in Computer Science 9843, 361372
doi.

K.K. Dabrowski, F. Dross and D. Paulusma,
Colouring diamondfree graphs,
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016),
Reykjavik, Iceland, June 2224, 2016,
Leibniz International Proceedings in Informatics 53, 16:116:14
doi.

P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
A linear kernel for finding square roots of almost planar graphs,
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016),
Reykjavik, Iceland, June 2224, 2016,
Leibniz International Proceedings in Informatics 53, 4:14:14
doi.

P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Squares of low clique number,
Proceedings of the 14th Cologne Twente Workshop 2016 (CTW 2016),
Gargnano, Italy, June 68, 2016,
Electronic Notes in Discrete Mathematics 55, 195198
doi.

K.K. Dabrowski, F. Dross, M. Johnson and D. Paulusma,
Filling the complexity gaps for colouring planar and bounded degree graphs,
Proceedings of the 26th International Workshop on Combinatorial Algorithms
(IWOCA 2015), Verona, Italy, October 57, 2015,
Lecture Notes in Computer Science 9538, 100111
doi.

A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma,
Bounding the cliquewidth of Hfree split graphs,
Proceedings of the 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
Bergen, Norway, August 31  September 4, 2015,
Electronic Notes in Discrete Mathematics 49, 497503
doi.

C. Feghali, M. Johnson and D. Paulusma,
Kempe equivalence of colourings of cubic graphs,
Proceedings of the 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
Bergen, Norway, August 31  September 4, 2015,
Electronic Notes in Discrete Mathematics 49, 243249
doi.

M. Johnson, D. Paulusma and E.J. van Leeuwen,
What graphs are 2dot product graphs?,
Proceedings of the 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
Bergen, Norway, August 31  September 4, 2015,
Electronic Notes in Discrete Mathematics 49, 705711
doi.

A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma, Bounding the cliquewidth of Hfree chordal graphs,
Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Milan, Italy, August 2428, 2015,
Lecture Notes in Computer Science 9235, 139150
doi.

T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma,
The price of connectivity for cycle transversals,
Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Milan, Italy, August 2428, 2015,
Lecture Notes in Computer Science 9235, 395406
doi.

P. Biro, W. Kern, D. Paulusma and P. Wojuteczky,
The stable fixtures problem with payments,
Proceedings of the 41th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2015),
Munich, Germany, June 1719, 2015,
Lecture Notes in Computer Science 9224, 4963
doi.

D. Paulusma,
Open problems on graph coloring for special graph classes,
Proceedings of the 41th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2015),
Munich, Germany, June 1719, 2015,
Lecture Notes in Computer Science 9224, 1630
doi.

M. Kaminski, D. Paulusma, A. Stewart and D.M. Thilikos,
Minimal disconnected cuts in planar graphs,
Proceedings of the 20th International Symposium on Fundamentals of Computation Theory (FCT 2015), Gdansk, Poland, August 1719, 2015,
Lecture Notes in Computer Science 9210, 243254
doi.

K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos,
Editing to a planar graph of given degrees,
Proceedings of the 10th International Computer Science Symposium in Russia (CSR 2015),
Listvyanka, Russia, July 1317, 2015,
Lecture Notes in Computer Science 9139, 143156
doi.

K.K. Dabrowski and D. Paulusma,
Cliquewidth of graph classes defined by two forbidden induced subgraphs,
Proceedings of the 9th International Conference on Algorithms and Complexity
(CIAC 2015), Paris, France, May 2022, 2015,
Lecture Notes in Computer Science 9079, 167181
doi.

O. Diner, D. Paulusma, C. Picouleau and B. Ries,
Contraction blockers for graphs with forbidden induced paths,
Proceedings of the 9th International Conference on Algorithms and Complexity
(CIAC 2015), Paris, France, May 2022, 2015,
Lecture Notes in Computer Science 9079, 194207
doi

K.K. Dabrowski, S. Huang and D. Paulusma, Bounding cliquewidth via perfect graphs,
Proceedings of the 9th International Conference on Language and Automata Theory and Applications
(LATA 2015), Nice, France, March 26, 2015,
Lecture Notes in Computer Science 8977, 676688
doi.

K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma, Editing to Eulerian graphs,
Proceedings of the 34th International Conference of Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2014), New Delhi, India, December 1517, 2014,
Leibniz International Proceedings in Informatics 29, 97108
doi.

M. Johnson, D. Kratsch, S. Kratsch, V. Patel and D. Paulusma,
Finding shortest paths between graph colourings,
Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Wroclaw, Poland, September 1012, 2014,
Lecture Notes in Computer Science 8894, 221233
doi.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen,
Induced disjoint paths in circulararc graphs in linear time,
Proceedings of the 40th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2014),
Domaine de Chales, France, June 2527, 2014,
Lecture Notes in Computer Science 8747, 225237
doi.

R. Belmonte, P. van 't Hof, M. Kaminski and D. Paulusma,
Forbidden induced subgraphs and the price of connectivity for feedback vertex set,
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014),
Budapest, Hungary, August 2529, 2014,
Lecture Notes in Computer Science 8635, 5768
doi.

C. Feghali, M. Johnson and D. Paulusma,
A reconfigurations analogue of Brooks' Theorem,
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014),
Budapest, Hungary, August 2529, 2014,
Lecture Notes in Computer Science 8635, 287298
doi.

M. Johnson, D. Paulusma and A. Stewart,
Knocking out Pkfree graphs,
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014),
Budapest, Hungary, August 2529, 2014,
Lecture Notes in Computer Science 8635, 396407
doi.

K.K. Dabrowski and D. Paulusma,
Classifying the cliquewidth of Hfree bipartite graphs,
Proceedings of the 20th International Computing and Combinatorics Conference (COCOON 2014),
Atlanta, Georgia, USA, August 46, 2014, Lecture Notes in Computer Science 8591, 489500
doi.

S. Huang, M. Johnson and D. Paulusma,
Narrowing the complexity gap for colouring (Cs,Pt)free graphs,
Proceedings of the 10th International Conference on Algorithmic Aspects of Information and Management (AAIM 2014),
Vancouver, Canada, July 811, 2014, Lecture Notes in Computer Science 8546, 162173
doi.

R. Belmonte, P. van 't Hof, M. Kaminski and D. Paulusma,
The price of connectivity for feedback vertex set,
Proceedings of the 7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2013), Pisa, Italy, September 9 13, 2013,
CRM Series 16, 123128
doi.

P.A. Golovach, D. Paulusma and I.A. Stewart,
Graph editing to a fixed target,
Proceedings of the 24th International Workshop on Combinatorial Algorithms
(IWOCA 2013), Rouen, France, July 1012, 2013,
Lecture Notes in Computer Science 8288, 192205
doi.

M. Johnson, D.Paulusma and E.J. van Leeuwen,
Algorithms to measure diversity and clustering in social networks through dot product graphs,
Proceedings of the 24th International Symposium on Algorithms and Computation
(ISAAC 2013), Hong Kong, China, December 1618, 2013, Lecture Notes in Computer Science 8283, 130140
doi.

R. Belmonte, P.A. Golovach, P. van 't Hof and D. Paulusma,
Parameterized complexity of two edge contraction problems with degree constraints,
Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Sophia Antipolis, France, September 46, 2013,
Lecture Notes in Computer Science 8246, 1627
doi.

H.J. Broersma, J. Fiala, P.A. Golovach, T. Kaiser, D. Paulusma and A. Proskurowski,
Lineartime algorithms for scattering number and hamiltonconnectivity of interval graphs,
Proceedings of the 39th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2013), Luebeck, Germany, June 1921, 2013,
Lecture Notes in Computer Science 8165, 127138
doi.

M. Cochefert, J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma,
Sparse square roots,
Proceedings of the 39th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2013), Luebeck, Germany, June 1921, 2013,
Lecture Notes in Computer Science 8165, 177188
doi.

K.K. Dabrowski, P.A. Golovach and D. Paulusma,
Colouring of graphs with Ramseytype forbidden subgraphs,
Proceedings of the 39th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2013), Luebeck, Germany, June 1921, 2013,
Lecture Notes in Computer Science 8165, 201212
doi.

S. Chaplick, J. Fiala, P. van 't Hof, D. Paulusma and M. Tesar,
Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree,
Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), Liverpool, UK, August 1921, 2013,
Lecture Notes in Computer Science 8070, 121132
doi.

P.A. Golovach and D. Paulusma,
List coloring in the absence of two subgraphs,
Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC 2013),
Barcelona, Spain, May 2224, 2013, Lecture Notes in Computer Science 7878, 288299
doi.

D. Paulusma, F. Slivovsky and S. Szeider,
Model counting for CNF formulas of bounded modular treewidth,
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013),
Kiel, Germany, February 27  March 2, 2013,
Leibniz International Proceedings in Informatics 20, 5566
doi.

P.A. Golovach, D. Paulusma and J. Song,
Closing complexity gaps for coloring problems on Hfree graphs,
Proceedings of the 23rd International Symposium on Algorithms and Computation
(ISAAC 2012), Taipei, Taiwan, December 1921, 2012,
Lecture Notes in Computer Science 7676, 1423
doi.

P.A. Golovach, D. Kratsch and D. Paulusma,
Detecting induced minors in ATfree graphs,
Proceedings of the 23nd International Symposium on Algorithms and Computation
(ISAAC 2012), Taipei, Taiwan, December 1921, 2012,
Lecture Notes in Computer Science 7676, 495505
doi.

P. Biro, M. Bomhoff, P.A. Golovach, W. Kern and D. Paulusma,
Solutions for the stable roommates problem with payments,
Proceedings of the 38th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2012), Jerusalem, Israel, June 2628, 2012,
Lecture Notes in Computer Science 7551, 6980
doi.

P.A. Golovach, P. Heggernes, P. van 't Hof, F. Manne, D. Paulusma and M. Pilipczuk,
How to eliminate a graph,
Proceedings of the 38th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2012), Jerusalem, Israel, June 2628, 2012,
Lecture Notes in Computer Science 7551, 320331
doi.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen, Induced disjoint paths in clawfree graphs,
Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012),
Ljubljana, Slovenia, September 1012, 2012, Lecture Notes in Computer Science 7501, 515526
doi.

P.A. Golovach, P. van 't Hof and D. Paulusma,
Obtaining planarity by contracting few edges,
Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012),
Bratislava, Slovakia, August 2731, 2012, Lecture Notes in Computer Science 7464, 455466
doi.

P.A. Golovach, D. Paulusma and B. Ries,
Coloring graphs characterized by a forbidden subgraph,
Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012),
Bratislava, Slovakia, August 2731, 2012, Lecture Notes in Computer Science 7464, 443454
doi.

R. Belmonte, P. van 't Hof, M. Kaminski, D. Paulusma and D.M. Thilikos,
Characterizing graphs of small carvingwidth,
Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012),
Banff, Canada, August 59, 2012, Lecture Notes in Computer Science 7402, 360370
doi.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen,
Induced disjoint paths in ATfree graphs,
Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Helsinki, Finland, July 46, 2012,
Lecture Notes in Computer Science 7357, 153164
doi.

P.A. Golovach, B. Lidicky, B. Martin and D. Paulusma,
Finding vertexsurjective graph homomorphisms,
Proceedings of the 7th International Computer Science Symposium in
Russia (CSR 2012), Nizhny Novgorod, Russia, July 37, 2012,
Lecture Notes in Computer Science 7353, 160171
doi.

P.A. Golovach, D. Paulusma and J. Song,
4Coloring Hfree graphs when H is small,
Proceedings of the 38th International Conference on Current Trends
in Theory and Practice of Computer Science (SOFSEM 2012),
Spindleruv Mlyn, Czech Republic, January 2127, 2012,
Lecture Notes in Computer Science 7147, 289300
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Increasing the minimum degree of a graph by contractions,
Proceedings of the 6th International Symposium on Parameterized and Exact Computation
(IPEC 2011), Saarbrucken, Germany, September 79, 2011,
Lecture Notes in Computer Science 7112 , 6779
doi

R. Belmonte, P.A. Golovach, P. Heggernes, P. van 't Hof, M. Kaminski and D. Paulusma, Finding contractions and induced minors in chordal graphs via disjoint paths,
Proceedings of the 22nd International Symposium on Algorithms and Computation
(ISAAC 2011), Yokohama, Japan, December 58, 2011,
Lecture Notes in Computer Science 7074, 110119
doi.

M. Bonamy, M. Johnson, I.M. Lignos, V. Patel and D. Paulusma,
On the diameter of reconfiguration graphs for vertex colourings,
Proceedings of the 6th European Conference on Combinatorics, Graph
Theory and Applications (EuroComb 2011), Budapest, Hungary, August 29  September 2, 2011,
Electronic Notes in Discrete Mathematics 38, 161166
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Lift contractions,
Proceedings of the 6th European Conference on Combinatorics, Graph
Theory and Applications (EuroComb 2011), Budapest, Hungary,
August 29  September 2, 2011,
Electronic Notes in Discrete Mathematics 38, 407412
doi.

J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma,
List coloring in the absence of a linear forest,
Proceedings of the 37th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2011), Tepla Monastery, Czech Republic,
June 2124, 2011,
Lecture Notes in Computer Science 6986, 119130
doi.

P.A. Golovach, D. Paulusma and J. Song,
Coloring graphs without short cycles and long induced paths,
Proceedings of the 18th International Symposium on Fundamentals of Computation Theory (FCT 2011), Oslo, Norway, August 2225, 2011,
Lecture Notes in Computer Science 6914, 193204
doi.

P.A. Golovach, M. Kaminski and D. Paulusma,
Contracting a chordal graph to a split graph or a tree,
Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), Warsaw, Poland, August 2226, 2011,
Lecture Notes in Computer Science 6907, 339350
doi.

B. Martin and D. Paulusma,
The computational complexity of Disconnected Cut and 2K2Partition,
Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011), Perugia, Italy, September 1216, 2011,
Lecture Notes in Computer Science 6876, 561575
doi.

S. Ordyniak, D. Paulusma and S. Szeider,
Satisfiability of acyclic and almost acyclic CNF formulas (II),
Proceedings of the 14th International Conference on
Theory and Applications of Satisfiability Testing
(SAT 2011), Ann Arbor, USA, June 1922, 2011,
Lecture Notes in Computer Science 6695, 4760
doi.

P.A. Golovach, D. Paulusma and J. Song,
Computing vertexsurjective homomorphisms to partially reflexive trees,
Proceedings of the 6th International Computer Science Symposium in
Russia
(CSR 2011), St. Petersburg, Russia, June 1418, 2011,
Lecture Notes in Computer Science 6651, 261274
doi.

S. Ordyniak, D. Paulusma and S. Szeider,
Satisfiability of acyclic and almost acyclic CNF formulas,
Proceedings of the 30th International Conference of Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2010), Chennai, India, December 1518, 2010,
Leibniz International Proceedings in Informatics 8, 8495
doi.

H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song,
On coloring graphs without induced forests,
Proceedings of the 21th International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, December 1517, 2010,
Lecture Notes in Computer Science 6507, 156167
doi.

P. Heggernes, P. van 't Hof and D. Paulusma,
Computing role assignments of proper interval graphs in polynomial time,
Proceedings of
the 21st International Workshop on Combinatorial Algorithms
(IWOCA 2010), London, UK, July 2628, 2010,
Lecture Notes in Computer Science 6460, 167180
doi.

H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song,
Narrowing down the gap on the complexity of coloring Pkfree graphs,
Proceedings of the 36th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2010),
Zaros, Crete, Greece, June 2830, 2010,
Lecture Notes in Computer Science 6410, 6374
doi.

M. Kaminski, D. Paulusma and D.M. Thilikos,
Contractions of planar graphs in polynomial time,
Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), Liverpool, UK, September 68, 2010, Lecture Notes in Computer Science 6346, 122133
doi.

P. Biro, W. Kern and D. Paulusma, On solution concepts for matching games,
Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, June 711, 2010,
Lecture Notes in Computer Science 6108, 117127
doi.

P.A. Golovach, B. Lidicky and D. Paulusma, L(2,1,1)labeling is NPcomplete for trees,
Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, June 711, 2010,
Lecture Notes in Computer Science 6108, 211221
doi.

J. Chalopin and D. Paulusma, Packing bipartite graphs with covers of complete bipartite graphs, Proceedings of the 7th International Conference
on Algorithms and Complexity (CIAC 2010), Rome, Italy, May 2628, 2010,
Lecture Notes in Computer Science 6078, 276287
doi.

M. Johnson, V. Patel, D. Paulusma and T. Trunck,
Obtaining online ecological colourings by generalizing firstfit,
Proceedings of the 5th International Computer Science Symposium in Russia
(CSR 2010), Kazan, Russia, June 1620, 2010, Lecture Notes in Computer Science 6072, 240251
doi.
 J. Fiala, M. Kaminski, B. Lidicky and D. Paulusma,
The kinapath problem for clawfree graphs,
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science
(STACS 2010), Nancy, France, March 46, 2010,
Leibniz International Proceedings in Informatics 5, 371382
doi.

P. van 't Hof, M. Kaminski, D. Paulusma, S. Szeider and D.M. Thilikos,
On contracting graphs to fixed pattern graphs,
Proceedings of the
36th Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM 2010), Spindleruv Mlyn, Czech Republic, January 2329, 2010,
Lecture Notes in Computer Science 5901, 503514
doi.

H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma,
Fast exact algorithms for hamiltonicity in clawfree graphs,
Proceedings of the 35th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2009),
Montpellier, France, June 2426, 2009, Lecture Notes in Computer Science 5911,
4453
doi.

P. van 't Hof, M. Kaminski and D. Paulusma,
Finding induced paths of given parity in clawfree graphs,
Proceedings of the 35th International Workshop on GraphTheoretic Concepts in Computer Science (WG 2009),
Montpellier, France, June 2426, 2009, Lecture Notes in Computer Science 5911,
341352
doi.

P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos,
Induced packing of odd cycles in a planar graph,
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009),
Honolulu, Hawaii, USA, December 1618, 2009, Lecture Notes in Computer Science
5878, 514523
doi.

T. Ito, M. Kaminski, D. Paulusma and D.M. Thilikos,
Parameterizing cut sets in a graph by the number of their components,
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009),
Honolulu, Hawaii, USA, December 1618, 2009, Lecture Notes in Computer Science
5878, 605615
doi.

D. Paulusma and J.M.M. van Rooij,
On partitioning a graph into two connected subgraphs,
Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009),
Honolulu, Hawaii, USA, December 1618, 2009, Lecture Notes in Computer Science
5878, 12151224
doi.

H.J. Broersma, F.V. Fomin, P.A. Golovach and D. Paulusma,
Three complexity results on coloring Pkfree graphs,
Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA 2009),
Hradec nad Moravici, Czech Republic, June 28July 2, 2009, Lecture Notes in Computer Science 5874, 95104
doi.

P. van 't Hof, D. Paulusma and J.M.M. van Rooij,
Computing role assignments of chordal graphs,
Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT 2009),
Wroclaw, Poland, September 24, 2009, Lecture Notes in Computer Science 5699, 193204 doi.
 P. van 't Hof, D. Paulusma and G.J. Woeginger,
Partitioning graphs into connected parts,
Proceedings of the 4th International Computer Science Symposium in Russia
(CSR 2009), Novosibirsk, Russia, August 1823, 2009, Lecture Notes in Computer Science 5675,
143154
doi.

M. Johnson, D. Paulusma and C. Wood,
Path factors and parallel knockout schemes of almost clawfree graphs,
Proceedings of the 19th International Workshop on Combinatorial Algorithms
(IWOCA 2008), Nagoya, Japan, September 1315, 2008, 2741.
 H.J. Broersma and D. Paulusma,
Computing sharp 2factors in clawfree graphs,
Proceedings of the 33th International Symposium on Mathematical Foundations of Computer
Science (MFCS 2008), Torun, Poland, August 2529, 2008,
Lecture Notes in Computer Science 5162, 193204
doi.
 P. van 't Hof and D. Paulusma,
A new characterization of P6free graphs,
Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON 2008),
Dalian, China, June 2729, 2008, Lecture Notes in Computer Science 5092, 415424
doi.
 J. Fiala and D. Paulusma, Comparing universal covers in polynomial time,
Proceedings of the 3rd International Computer Science Symposium in Russia (CSR 2008), Moscow, Russia, June 712, 2008, Lecture Notes in Computer Science 5010, 158167
doi.

H. Fleischner, E. Mujuni, D. Paulusma and S. Szeider,
Covering graphs with few complete bipartite subgraphs,
Proceedings of the 27th International Conference of Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2007), New Delhi, India, December 1214, 2007, Lecture Notes in Computer Science 4855, 340351
doi.

H.J. Broersma, D. Paulusma and K. Yoshimoto, On components of 2factors in clawfree graphs,
Proceedings of the 4th European Conference on Combinatorics, Graph
Theory and Applications (EuroComb 2007), Seville, Spain, September 1115, 2007,
Electronic Notes in Discrete Mathematics 29, 289293
doi.

H.J. Broersma, M. Johnson and D. Paulusma,
Upper bounds and algorithms for parallel knockout numbers,
Proceedings of the 14th International Colloquium on Structural Information
and Communication Complexity (SIROCCO 2007), Castiglioncello, Italy, June 58, 2007,
Lecture Notes in Computer Science 4474, 328340
doi.

H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman,
Improved upper bounds for lbackbone colorings along matchings and stars,
Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM 2007), Harrachov, Czech Republic, January 2026, 2007, Lecture Notes in Computer Science 4362,
188199
doi.

J. Chalopin and D. Paulusma, Graph labelings derived from models in distributed computing,
Proceedings of the 32st International Workshop on GraphTheoretic Concepts
in Computer Science (WG 2006), Bergen, Norway, June 2224, 2006, Lecture Notes in Computer
Science 4271, 301312
doi.

H.J. Broersma, A. Capponi and D. Paulusma,
Online coloring of Hfree bipartite graphs,
Proceedings of the 6th International Conference on Algorithms and Complexity
(CIAC 2006), Rome, Italy, May 2931, 2006, Lecture Notes in Computer Science 3998,
284295
doi.

H.J. Broersma, M. Johnson, D. Paulusma and I.A. Stewart,
The computational complexity of the parallel knockout problem,
Proceedings of the 7th Latin American Theoretical Informatics Symposium
(LATIN 2006), Valdivia, Chile, March 2024, 2006,
Lecture Notes in Computer Science 3887, 250261
doi.

J. Fiala, D. Paulusma and J.A. Telle,
Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms,
Proceedings of the 31st International Workshop on GraphTheoretic Concepts
in Computer Science (WG 2005), Metz, France, June 2325, 2005, Lecture Notes in Computer
Science 3787, 115226
doi.

J. Fiala, D. Paulusma and J.A. Telle,
Matrix and graph orders derived from locally constrained graph homomorphisms,
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer
Science (MFCS 2005), Gdansk, Poland, August 29September 2, 2005,
Lecture Notes in Computer Science 3618, 340351
doi.
 L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma and P.T. Wolkotte, Runtime mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture,
Proceedings of the 3rd IEEE International Conference on FieldProgrammable Technology (FPT 2004), Brisbane, Australia,
December 68, 2004, 421424
doi.
 L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma and P.T. Wolkotte,
Runtime assignment of tasks to multiple heterogeneous processors.
Proceedings of the 5th PROGRESS Symposium on Embedded Systems, Nieuwegein, The Netherlands, October 20,
2004, 185192.
 H.J. Broersma, D. Paulusma, G.J.M. Smit, F. Vlaardingerbroek and G.J. Woeginger,
The computational complexity of the minimum weight processor assignment problem,
Proceedings of the 30th International Workshop on GraphTheoretic Concepts
in Computer Science (WG 2004), Bad Honnef, Germany, June 2123, 2004, Lecture Notes in Computer
Science 3353, 189200
doi.
 A. Levin, D. Paulusma and G.J. Woeginger, The complexity of graph contractions,
Proceedings of the 29th International Workshop on GraphTheoretic Concepts
in Computer Science (WG 2003), Elspeet, the Netherlands, June 1921, 2003, Lecture Notes in Computer Science 2880, 322333
doi.
 J. Fiala and D. Paulusma,
The computational complexity of the role assignment problem,
Proceedings of the 30th International Colloquium on Automata, Languages and Programming
(ICALP 2003), Eindhoven, The Netherlands, June 30July 4, 2003,
Lecture Notes in Computer Science 2719, 817828
doi.
Submitted Journal Papers

J. Bok, N. Jedlickova, B. Martin, P. Ochem, D. Paulusma and S. Smith, Acyclic, star and injective colouring: a complexity picture for Hfree graphs.

N. Brettell, J. Horsfield, A. Munaro, G. Paesani and D. Paulusma,
Bounding the mimwidth of hereditary graph classes.

N. Brettell, J. Horsfield, A. Munaro and D. Paulusma, List kColouring P_tfree graphs: a mimwidth perspective.

N. Brettell, M. Johnson, G. Paesani and D. Paulusma, Computing subset transversals in Hfree graphs.

K.K. Dabrowski, F. Dross, J. Jeong, M.M. Kante, O. Kwon, S. Oum and D. Paulusma, Tree pivotminors and linear rankwidth.

K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev,
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.

K.K. Dabrowski, T. Masarik, J. Novotna, D. Paulusma and P. Rzazewski,
Cliquewidth: harnessing the power of atoms.

P.A. Golovach, D. Paulusma and E.J. van Leeuwen,
Induced disjoint paths in ATfree graphs.

M. Johnson, D. Paulusma and E.J. van Leeuwen,
What graphs are 2dot product graphs?

B. Martin, D. Paulusma and S. Smith, Colouring graphs of bounded diameter in the absence of small cycles.

B. Martin, D. Paulusma and S. Smith, Hard problems that quickly become very easy.
Other Manuscripts

D. Allison and D. Paulusma, New bounds for the SnakeintheBox problem.

G. Berthe, B. Martin, D. Paulusma and S. Smith, The complexity of L(p,q)EdgeLabelling.

M. Benedek, P. Biro, W. Kern and D. Paulusma, Computing international kidney exchange schemes.

C. Brause, P.A. Golovach, B. Martin, D. Paulusma and S. Smith, Partitioning Hfree graphs of bounded diameter.

E. Galby, P.T. Lima, D. Paulusma and B. Ries,
On the parametrized complexity of kEdge Colouring.

B. Larose, P. Markovic, B. Martin, D. Paulusma, S. Smith, and S. Zivny, QCSP on reflexive tournaments.

G. Paesani, D. Paulusma and P. Rzazewski, Feedback Vertex Set and Even Cycle Transversal for
Hfree graphs: finding large block graphs.

D. Paulusma, On finding paths passing through specified vertices.
For preprints see
here.