Preprints

Some of the preprints may go or may have gone through additional rounds of changes before publication. The copyright of the published papers is with the respective publishers.
  1. D. Allison and D. Paulusma, New bounds for the Snake-in-the-Box problem. [arXiv]
  2. 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. [pdf-file]
  3. R. Belmonte, P.A. Golovach, P. van 't Hof and D. Paulusma, Parameterized complexity of three edge contraction problems with degree constraints. [pdf-file]
  4. R. Belmonte, P. van 't Hof, M. Kaminski and D. Paulusma, The price of connectivity for feedback vertex set. [arXiv]
  5. R. Belmonte, P. van 't Hof, M. Kaminski, D. Paulusma and D.M. Thilikos, Characterizing graphs of small carving-width. [pdf-file]
  6. P. Biro, M. Bomhoff, P.A. Golovach, W Kern and Daniel Paulusma, Solutions for the stable roommates problem with payments. [pdf-file]
  7. P. Biro, W. Kern and D. Paulusma, Computing solutions for matching games. [pdf-file]
  8. P. Biro, W. Kern, D. Paulusma and P. Wojuteczky, The stable fixtures problem with payments. [arXiv]
  9. A. Blanche, K.K. Dabrowski, M. Johnson, V.V. Lozin, D. Paulusma and V. Zamaraev, Clique-width for graph classes closed under complementation. [arXiv]
  10. A. Blanche, K.K. Dabrowski, M. Johnson and D. Paulusma, Hereditary graph classes: when the complexities of Colouring and Clique Cover coincide. [arXiv]
  11. M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma, Independent feedback vertex set for P5-free graphs. [arXiv]
  12. M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma, Independent feedback vertex sets for graphs of bounded diameter. [arXiv]
  13. M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration. [arXiv]
  14. M. Bonamy, M. Johnson, I.M. Lignos, V. Patel and D. Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. [pdf-file]
  15. P. Bonsma and D. Paulusma, Using contracted solution graphs for solving reconfiguration problems. [arXiv]
  16. A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma, Bounding the clique-width of H-free chordal graphs. [arXiv]
  17. A. Brandstadt, K.K. Dabrowski, S. Huang and D. Paulusma, Bounding the clique-width of H-free split graphs. [arXiv]
  18. H.J. Broersma, A. Capponi and D. Paulusma, A new algorithm for on-line coloring bipartite graphs. [pdf-file]
  19. H.J. Broersma, J. Fiala, P.A. Golovach, T. Kaiser, D. Paulusma and A. Proskurowski, Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. [pdf-file]
  20. H.J. Broersma, F.V. Fomin, P.A. Golovach and D. Paulusma, Three complexity results on coloring Pk-free graphs. [pdf-file]
  21. H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma, Exact algorithms for finding longest cycles in claw-free graphs. [pdf-file]
  22. H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto, l-Backbone colorings along pairwise disjoint stars and matchings. [pdf-file]
  23. H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song, Updating the complexity status of coloring graphs without a fixed induced linear forest. [pdf-file]
  24. H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song, Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. [pdf-file]
  25. H.J. Broersma, M. Johnson and D. Paulusma, Upper bounds and algorithms for parallel knock-out numbers. [pdf-file]
  26. H.J. Broersma, M. Johnson, D. Paulusma and I.A. Stewart, The computational complexity of the parallel knock-out problem. [pdf-file]
  27. 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. [pdf-file]
  28. 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. [pdf-file]
  29. H.J. Broersma and D. Paulusma, Computing sharp 2-factors in claw-free graphs. [pdf-file]
  30. H.J. Broersma, D. Paulusma and K. Yoshimoto, Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. [pdf-file]
  31. J. Chalopin and D. Paulusma, Graph labelings derived from models in distributed computing: a complete complexity classification. [pdf-file]
  32. J. Chalopin and D. Paulusma, Packing bipartite graphs with covers of complete bipartite graphs. [pdf-file]
  33. S. Chaplick, J. Fiala, P. van 't Hof, D. Paulusma and M. Tesar, Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. [arXiv]
  34. 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. [arXiv]
  35. M. Cochefert, J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma, Parameterized algorithms for finding square roots. [pdf-file]
  36. M. Cochefert, J.F. Couturier, P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart, Squares of low maximum degree. [arXiv]
  37. J.F. Couturier, P.A. Golovach, D. Kratsch and D. Paulusma, List coloring in the absence of a linear forest. [pdf-file]
  38. 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. [pdf-file]
  39. K.K. Dabrowski, F. Dross, M. Johnson and D. Paulusma, Filling the complexity gaps for colouring planar and bounded degree graphs. [arXiv]
  40. K.K. Dabrowski, F. Dross and D. Paulusma, Colouring diamond-free graphs. [arXiv]
  41. K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma, Editing to Eulerian graphs. [arXiv]
  42. K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos, Editing to a planar graph of given degrees. [arXiv]
  43. K.K. Dabrowski, P.A. Golovach and D. Paulusma, Colouring of graphs with Ramsey-type forbidden subgraphs. [pdf-file]
  44. K.K. Dabrowski, S. Huang and D. Paulusma, Bounding clique-width via perfect graphs. [arXiv]
  45. K.K. Dabrowski, V. Lozin and D. Paulusma, Clique-width and well-quasi ordering of triangle-free graph classes. [arXiv]
  46. K.K. Dabrowski, V. Lozin and D. Paulusma, Well-quasi-ordering versus clique-width: new results on bigenic classes. [arXiv]
  47. K.K. Dabrowski and D. Paulusma, Clique-width of graph classes defined by two forbidden induced subgraphs. [arXiv]
  48. K.K. Dabrowski and D. Paulusma, Classifying the clique-width of H-free bipartite graphs. [pdf-file]
  49. K.K. Dabrowski and D. Paulusma, Contracting bipartite graphs to paths and cycles. [arXiv]
  50. K.K. Dabrowski and D. Paulusma, On colouring (2P2,H)-free and (P5,H)-free graphs. [arXiv]
  51. O. Diner, D. Paulusma, C. Picouleau and B. Ries, Contraction and deletion blockers for perfect graphs and H-free graphs. [arXiv]
  52. T.S.H. Driessen and D. Paulusma, Two extensions of the Shapley value for cooperative games. [pdf-file]
  53. U. Faigle, W. Kern and D. Paulusma, Note on the computational complexity of least core concepts for min-cost spanning tree games. [pdf-file]
  54. C. Feghali, M. Johnson and D. Paulusma, A reconfigurations analogue of Brooks' Theorem and its consequences. [pdf-file]
  55. C. Feghali, M. Johnson and D. Paulusma, Kempe equivalence of colourings of cubic graphs. [arXiv]
  56. J. Fiala, P.A. Golovach, J. Kratochvil, B. Lidicky ad D. Paulusma, Distance three labelings of trees. [pdf-file]
  57. J. Fiala, M. Kaminski, B. Lidicky and D. Paulusma, The k-in-a-path problem for claw-free graphs. [pdf-file]
  58. J. Fiala, M. Kaminski and D. Paulusma, A note on contracting claw-free graphs. [pdf-file]
  59. J. Fiala, M. Kaminski and D. Paulusma, Detecting induced star-like minors in polynomial time. [pdf-file]
  60. J. Fiala and D. Paulusma, A complete complexity classification of the role assignment problem. [pdf-file]
  61. J. Fiala and D. Paulusma, Comparing universal covers in polynomial time. [pdf-file]
  62. J. Fiala, D. Paulusma and J.A. Telle, Locally constrained graph homomorphisms and equitable partitions. [pdf-file]
  63. H. Fleischner, E. Mujuni, D. Paulusma and S. Szeider, Covering graphs with few complete bipartite subgraphs. [pdf-file]
  64. P.A. Golovach, P. Heggernes, P. van 't Hof, F. Manne, D. Paulusma and M. Pilipczuk, Modifying a graph using vertex elimination. [pdf-file]
  65. P.A. Golovach, P. Heggernes, P. van 't Hof and D. Paulusma, Choosability on H-free graphs. [pdf-file]
  66. 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. [arXiv]
  67. P.A. Golovach, P. van 't Hof and D. Paulusma, Obtaining planarity by contracting few edges. [pdf-file]
  68. P.A. Golovach, M. Johnson, B. Martin, D. Paulusma and A. Stewart, Surjective H-Colouring: new hardness results. [arXiv]
  69. P.A. Golovach, M. Johnson, D. Paulusma and J. Song, A survey on the computational complexity of colouring graphs with forbidden subgraphs. [arXiv]
  70. P.A. Golovach, M. Kaminski and D. Paulusma, Contracting a chordal graph to a split graph or a tree. [pdf-file]
  71. P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos, Containment relations in split graphs. [pdf-file]
  72. P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos, Increasing the minimum degree of a graph by contractions. [pdf-file]
  73. P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos, Induced packing of odd cycles in planar graphs. [pdf-file]
  74. P.A. Golovach, M. Kaminski, D. Paulusma and D.M. Thilikos, Lift-contractions. [pdf-file]
  75. P.A. Golovach, D. Kratsch and D. Paulusma, Detecting induced minors in AT-free graphs. [pdf-file]
  76. P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart, A linear kernel for finding square roots of almost planar graphs. [arXiv]
  77. P.A. Golovach, D. Kratsch, D. Paulusma and A. Stewart, Finding cactus roots in polynomial time. [pdf-file]
  78. P.A. Golovach, B. Lidicky, B. Martin and D. Paulusma, Finding vertex-surjective graph homomorphisms. [pdf-file]
  79. P.A. Golovach and D. Paulusma, List coloring in the absence of two subgraphs. [pdf-file]
  80. P.A. Golovach, D. Paulusma and B. Ries, Coloring graphs characterized by a forbidden subgraph. [pdf-file]
  81. P.A. Golovach, D. Paulusma and J. Song, Closing complexity gaps for coloring problems on H-free graphs. [pdf-file]
  82. P.A. Golovach, D. Paulusma and J. Song, Coloring graphs without short cycles and long induced paths. [pdf-file]
  83. P.A. Golovach, D. Paulusma and J. Song, Computing vertex-surjective homomorphisms to partially reflexive trees. [pdf-file]
  84. P.A. Golovach, D. Paulusma and J. Song, 4-Coloring H-free graphs when H Is small. [pdf-file]
  85. P.A. Golovach, D. Paulusma and I.A. Stewart, Graph editing to a fixed target. [pdf-file]
  86. P.A. Golovach, D. Paulusma and E.J. van Leeuwen, Induced disjoint paths in circular-arc graphs in linear time. [pdf-file]
  87. P.A. Golovach, D. Paulusma and E.J. van Leeuwen, Induced disjoint paths in claw-free graphs. [pdf-file]
  88. T.R. Hartinger, M. Johnson, M. Milanic and D. Paulusma, The price of connectivity for cycle transversals. [pdf-file]
  89. P. Heggernes, P. van 't Hof and D. Paulusma, Computing role assignments of proper interval graphs in polynomial time. [pdf-file]
  90. P. van 't Hof, M. Kaminski and D. Paulusma, Finding induced paths of given parity in claw-free graphs. [pdf-file]
  91. P. van 't Hof, M. Kaminski, D. Paulusma, S. Szeider and D.M. Thilikos, On graph contractions and induced minors. [pdf-file]
  92. P. van 't Hof and D. Paulusma, A new characterization of P6-free graphs. [pdf-file]
  93. P. van 't Hof, D. Paulusma and J.M.M. van Rooij, Computing role assignments of chordal graphs. [pdf-file]
  94. P. van 't Hof, D. Paulusma and G.J. Woeginger, Partitioning graphs into connected parts. [pdf-file]
  95. S. Huang, M. Johnson and D. Paulusma, Narrowing the complexity gap for colouring (Cs,Pt)-free graphs. [arXiv]
  96. T. Ito, M. Kaminski, D. Paulusma, and D.M. Thilikos, On disconnected cuts and separators. [pdf-file]
  97. T. Ito, M. Kaminski, D. Paulusma, and D.M. Thilikos, Parameterizing cut sets in a graph by the number of their components. [pdf-file]
  98. M. Johnson, V. Patel, D. Paulusma and T. Trunck, Obtaining online ecological colourings by generalizing first-fit. [pdf-file]
  99. M. Johnson, D. Kratsch, S. Kratsch, V. Patel and D. Paulusma, Finding shortest paths between graph colourings. [arXiv]
  100. M. Johnson, D. Paulusma and A. Stewart, Knocking out Pk-free graphs. [pdf-file]
  101. M. Johnson, D. Paulusma and E.J. van Leeuwen, Algorithms to measure diversity and clustering in social networks through dot product graphs. [pdf-file]
  102. M. Johnson, D. Paulusma and E.J. van Leeuwen, What graphs are 2-dot product graphs? [arXiv]
  103. M. Johnson, D. Paulusma and C. Wood, Path factors and parallel knock-out schemes of almost claw-free graphs. [pdf-file]
  104. M. Kaminski, D. Paulusma, A. Stewart and D.M. Thilikos, Minimal disconnected cuts in planar graphs. [pdf-file]
  105. M. Kaminski, D. Paulusma and D.M. Thilikos, Contractions of graphs on surfaces in polynomial time. [pdf-file]
  106. M. Kaminski, D. Paulusma and D.M. Thilikos, Contracting planar graphs to contractions of triangulations. [pdf-file]
  107. W. Kern and D. Paulusma, On the core and f-nucleolus of flow games. [pdf-file]
  108. W. Kern and D. Paulusma, Matching games: the least core and the nucleolus. [pdf-file]
  109. W. Kern and D. Paulusma, The computational complexity of the elimination problem in generalized sports competitions. [pdf-file]
  110. W. Kern and D. Paulusma, The new FIFA rules are hard: complexity aspects of sport competitions. [pdf-file]
  111. B. Larose, B. Martin and D. Paulusma, Surjective H-Colouring over reflexive digraphs. [arXiv]
  112. A. Levin, D. Paulusma and G.J. Woeginger, The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. [pdf-file]
  113. A. Levin, D. Paulusma and G.J. Woeginger, The computational complexity of graph contractions II: two tough polynomially solvable cases. [pdf-file]
  114. B. Martin and D. Paulusma, The computational complexity of Disconnected Cut and 2K2-Partition. [pdf-file]
  115. S. Ordyniak, D. Paulusma and S. Szeider, Satisfiability of acyclic and almost acyclic CNF formulas. [pdf-file]
  116. D. Paulusma, Complexity Aspects of Cooperative Games. [pdf-file]
  117. D. Paulusma, Open problems on graph coloring for special graph classes. [pdf-file]
  118. D. Paulusma, C. Picouleau and B. Ries, Critical vertices and edges in H-free graphs. [arXiv]
  119. D. Paulusma and J.M.M. van Rooij, On partitioning a graph into two connected subgraphs. [pdf-file]
  120. D. Paulusma, F. Slivovsky and S. Szeider, Model counting for CNF formulas of bounded modular treewidth. [pdf-file]
  121. D. Paulusma and K. Yoshimoto, Cycles through specified vertices in triangle-free graphs. [pdf-file]
  122. D. Paulusma and K. Yoshimoto, Relative length of longest paths and longest cycles in triangle-free graphs. [pdf-file]
  123. L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma and P.T. Wolkotte, Run-time assignment of tasks to multiple heterogeneous processors. [pdf-file]
  124. L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma and P.T. Wolkotte, Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. [pdf-file]