All Outputs (7)

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.

Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs (2009)
Journal Article
Broersma, H., Paulusma, D., & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25(4), 427-460. https://doi.org/10.1007/s00373-009-0855-7

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 compo... Read More about Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs.

On the core and f-nucleolus of flow games (2009)
Journal Article
Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405

Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124–131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2... Read More about On the core and f-nucleolus of flow games.

λ-backbone colorings along pairwise disjoint stars and matchings (2009)
Journal Article
Broersma, H., Fujisawa, J., Marchal, L., Paulusma, D., Salman, A., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007

Given an integer λ≥2, a graph G=(V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G,H) is a proper vertex coloring V→{1,2,…} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. We study... Read More about λ-backbone colorings along pairwise disjoint stars and matchings.

Covering graphs with few complete bipartite subgraphs (2009)
Journal Article
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the bicliq... Read More about Covering graphs with few complete bipartite subgraphs.

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number (2009)
Journal Article
Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, 29(1), 143-162. https://doi.org/10.7151/dmgt.1437

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a l-backbone coloring for G and H is a proper vertex col... Read More about Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.

Upper bounds and algorithms for parallel knock-out numbers (2009)
Journal Article
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.