Outputs (6)

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.

Finding Induced Paths of Given Parity in Claw-Free Graphs (2009)
Conference Proceeding
Hof van 't, P., Kaminski, M., & Paulusma, D. (2009). Finding Induced Paths of Given Parity in Claw-Free Graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science (341-352). https://doi.org/10.1007/978-3-642-11409-0_30

The Parity Path problem is to decide if a given graph G contains both an odd length and an even length induced path between two specified vertices s and t. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine wheth... Read More about Finding Induced Paths of Given Parity in Claw-Free Graphs.

Partitioning graphs into connected parts (2009)
Journal Article
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pat... Read More about Partitioning graphs into connected parts.

Computing role assignments of chordal graphs (2009)
Conference Proceeding
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009). Computing role assignments of chordal graphs. In Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings (193-204). https://doi.org/10.1007/978-3-642-03409-1_18

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.

Partitioning graphs into connected parts (2009)
Conference Proceeding
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. In Computer science - theory and applications (143-154). https://doi.org/10.1007/978-3-642-03351-3_15

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pa... Read More about Partitioning graphs into connected parts.

A new characterization of P6-free graphs (2008)
Conference Proceeding
Hof, P. V., & Paulusma, D. (2008). A new characterization of P6-free graphs. In X. Hu, & J. Wang (Eds.), Computing and combinatorics, 14th Annual International Conference, COCOON 2008, 27-29 June 2008 Dalian, China ; proceedings (415-424). https://doi.org/10.1007/978-3-540-69733-6_41

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.