All Outputs (4)

Finding Induced Paths of Given Parity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Hof van 't, P., Kaminski, M., & Paulusma, D. (2009, December). Finding Induced Paths of Given Parity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science, Montpellier, France

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.

Computing role assignments of chordal graphs (2009)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009, September). Computing role assignments of chordal graphs. Presented at 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw, Poland

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)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009, August). Partitioning graphs into connected parts. Presented at Fourth International Computer Science Symposium in Russia (CSR 2009)., Novosibirsk, Russia

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)
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.