Obtaining online ecological colourings by generalizing first-fit (2010)
Conference Proceeding
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. . https://doi.org/10.1007/978-3-642-13182-0_22

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Computing role assignments of chordal graphs (2010)
Journal Article
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,…,k}, called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles a... Read More about Computing role assignments of chordal graphs.

Computing sharp 2-factors in claw-free graphs (2010)
Journal Article
Broersma, H., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. https://doi.org/10.1016/j.jda.2009.07.001

In a previous 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 paper we... Read More about Computing sharp 2-factors in claw-free graphs.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Journal Article
Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310(9), 1413-1423. https://doi.org/10.1016/j.disc.2009.04.022

An H1,{H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2. We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.

Comparing universal covers in polynomial time (2010)
Journal Article
Fiala, J., & Paulusma., D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems, 46(4), 620-635. https://doi.org/10.1007/s00224-009-9200-z

The universal cover T G of a connected graph G is the unique (possibly infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. It is well-known that if a graph G covers a graph H, then their universal covers are i... Read More about Comparing universal covers in polynomial time.

A new characterization of P6-free graphs (2010)
Journal Article
Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025

We study P6-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 P6-free if and only if each connected induced subgraph of G on more than one vertex... Read More about A new characterization of P6-free graphs.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Conference Proceeding
Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. In M. Miller, & K. Wada (Eds.), Proceedings of the International Workshop on Combinatorial Algorithms 2008 (27-41). https://doi.org/10.1016/j.disc.2009.04.022

An H1, {H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2.We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.

L(2,1,1)-labeling is NP-complete for trees (2010)
Conference Proceeding
Golovach, P. A., Lidicky, B., & Paulusma, D. (2010). L(2,1,1)-labeling is NP-complete for trees. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_20

An L(p 1,p 2,p 3)-labeling of a graph G with span λ is a mapping f that assigns each vertex u of G an integer label 0 ≤ f(u) ≤ λ such that |f(u) − f(v)| ≥ p i whenever vertices u and v are of distance i for i ∈ {1,2,3}. We show that testing whether a... Read More about L(2,1,1)-labeling is NP-complete for trees.

On contracting graphs to fixed pattern graphs (2010)
Conference Proceeding
't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010). On contracting graphs to fixed pattern graphs. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23-29 January 2010 ; proceedings (503-514). https://doi.org/10.1007/978-3-642-11266-9_42

For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a domina... Read More about On contracting graphs to fixed pattern graphs.

On solution concepts for matching games (2010)
Conference Proceeding
Biro, P., Kern, W., & Paulusma, D. (2010). On solution concepts for matching games. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_12

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an... Read More about On solution concepts for matching games.

Packing bipartite graphs with covers of complete bipartite graphs (2010)
Conference Proceeding
Chalopin, J., & Paulusma, D. (2010). Packing bipartite graphs with covers of complete bipartite graphs. In T. Calamoneri, & J. Diaz (Eds.), Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings (276-287). https://doi.org/10.1007/978-3-642-13073-1_25

For a set of graphs, a perfect -packing (-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of and that together contain all vertices of G. If G allows a covering (locally bijective homomorp... Read More about Packing bipartite graphs with covers of complete bipartite graphs.

The k-in-a-path problem for claw-free graphs (2010)
Conference Proceeding
Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010). The k-in-a-path problem for claw-free graphs. In J. Marion, & T. Schwentick (Eds.), 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings (371-382). https://doi.org/10.4230/lipics.stacs.2010.2469

Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an a... Read More about The k-in-a-path problem for claw-free graphs.

Contractions of planar graphs in polynomial time (2010)
Conference Proceeding
Kaminski, M., Paulusma, D., & Thilikos, D. (2010). Contractions of planar graphs in polynomial time. In Algorithms : ESA 2010 : 18th Annual European Symposium, 6-8 September 2010, Liverpool UK ; proceedings part I (122-133). https://doi.org/10.1007/978-3-642-15775-2_11

We prove that for every graph H, there exists a polynomial-time algorithm deciding if a planar graph can be contracted to H. We introduce contractions and topological minors of embedded (plane) graphs and show that a plane graph H is an embedded cont... Read More about Contractions of planar graphs in polynomial time.