Editing to Eulerian graphs (2015)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and dir... Read More about Editing to Eulerian graphs.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, https://doi.org/10.1093/comjnl/bxv096

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Narrowing the complexity gap for colouring (Cs, Pt)-free graphs (2015)
Journal Article
Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039

For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem... Read More about Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences (2015)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper co... Read More about A Reconfigurations Analogue of Brooks' Theorem and Its Consequences.

Knocking out P_k-free graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking out P_k-free graphs.

Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree (2015)
Journal Article
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether... Read More about Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree.

Model counting for CNF formulas of bounded modular treewidth (2015)
Journal Article
Paulusma, D., Slivovsky, S., & Szeider, S. (2016). Model counting for CNF formulas of bounded modular treewidth. Algorithmica, 76(1), 168-194. https://doi.org/10.1007/s00453-015-0030-x

We define the modular treewidth of a graph as its treewidth after contraction of modules. This parameter properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments can be compu... Read More about Model counting for CNF formulas of bounded modular treewidth.

Classifying the clique-width of H-free bipartite graphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030

Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induce... Read More about Classifying the clique-width of H-free bipartite graphs.

Finding Shortest Paths Between Graph Colourings (2015)
Journal Article
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successiv... Read More about Finding Shortest Paths Between Graph Colourings.

Algorithms for diversity and clustering in social networks through dot product graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector View... Read More about Algorithms for diversity and clustering in social networks through dot product graphs.

Coloring graphs characterized by a forbidden subgraph (2015)
Journal Article
Golovach, P., Paulusma, D., & Ries, B. (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics, 180, 101-110. https://doi.org/10.1016/j.dam.2014.08.008

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an in... Read More about Coloring graphs characterized by a forbidden subgraph.

Induced disjoint paths in claw-free graphs (2015)
Journal Article
Golovach, P., Paulusma, D., & van Leeuwen, E. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics, 29(1), 348-375. https://doi.org/10.1137/140963200

Paths P1; : : : ; Pk in a graph G = (V;E) are said to be mutually induced if for any 1 i < j k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a... Read More about Induced disjoint paths in claw-free graphs.