Outputs (6)

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Hof van 't, P., & Paulusma, D. (2009, June). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France

The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O *(α n ) time for some constant α< 2 is a no...

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.

Three complexity results on coloring Pk-free graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2023, June). Three complexity results on coloring Pk-free graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic

We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring rema... Read More about Three complexity results on coloring Pk-free graphs.

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

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.

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.