Professor Daniel Paulusma's Outputs (9)

The computational complexity of graph contractions II: two tough polynomially solvable cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52(1), 32-56. https://doi.org/10.1002/net.20249

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This article is part II of our study on the computational complexity of the H-CONTRACTIBILITY problem. In the first ar... Read More about The computational complexity of graph contractions II: two tough polynomially solvable cases.

A new characterization of P6-free graphs (2008)
Presentation / Conference Contribution
Hof, P. V., & Paulusma, D. (2008, December). A new characterization of P6-free graphs. Presented at 14th Annual International Computing and Combinatorics Conference, Dalian, China

We study P 6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P 6-free if and only if each connected induced subgraph of G on more than one vert... Read More about A new characterization of P6-free graphs.

The computational complexity of graph contractions I: polynomially solvable and NP-complete cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51(3), 178-189. https://doi.org/10.1002/net.20214

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This paper is part I of our study on the computational complexity of the H-CONTRACTIBILITY problem. We continue a line... Read More about The computational complexity of graph contractions I: polynomially solvable and NP-complete cases.

Locally constrained graph homomorphisms and equitable partitions (2008)
Journal Article
Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006

We explore the connection between locally constrained graph homomorphisms and degree matrices arising from an equitable partition of a graph. We provide several equivalent characterizations of degree matrices. As a consequence we can efficiently chec... Read More about Locally constrained graph homomorphisms and equitable partitions.

Relative length of longest paths and longest cycles in triangle-free graphs (2008)
Journal Article
Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |VPVC|1, or G is isomorph... Read More about Relative length of longest paths and longest cycles in triangle-free graphs.

The computational complexity of the parallel knock-out problem (2008)
Journal Article
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

A new algorithm for on-line coloring bipartite graphs (2008)
Journal Article
Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675

We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs... Read More about A new algorithm for on-line coloring bipartite graphs.

Computing sharp 2-factors in claw-free graphs (2008)
Presentation / Conference Contribution
Broersma, H. J., & Paulusma, D. (2008, December). Computing sharp 2-factors in claw-free graphs. Presented at 33th International Symposium on Mathematical Foundations of Computer Science, Toru´n, Poland

In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this... Read More about Computing sharp 2-factors in claw-free graphs.

Comparing universal covers in polynomial time (2008)
Presentation / Conference Contribution
Fiala, J., & Paulusma, D. (2008, December). Comparing universal covers in polynomial time. Presented at 3rd International Computer Science Symposium in Russia, Moscow, Russia

The universal cover T G of a connected graph G is the unique (possible infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. Universal covers have major applications in the area of distributed computing. It is w... Read More about Comparing universal covers in polynomial time.