Skip to main content

Research Repository

Advanced Search

All Outputs (14)

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs (2009)
Presentation / Conference Contribution

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 α

Fully decomposable split graphs (2009)
Conference Proceeding
Broersma, H., Kratsch, D., & Woeginger, G. (2009). Fully decomposable split graphs. In Combinatorial algorithms : 20th International Workshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers (105-112). https://doi.org/10.1007/978-3-642-10217-2_13

We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, i.e., whether it can be partitioned into connected par... Read More about Fully decomposable split graphs.

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.

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

On hamiltonicity of P3-dominated graphs (2009)
Journal Article
Broersma, H., & Vumar, E. (2009). On hamiltonicity of P3-dominated graphs. Mathematical Methods of Operations Research, 69(2), 297-306. https://doi.org/10.1007/s00186-008-0260-7

We introduce a new class of graphs which we call P₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P₃-dominated graph. We prove that G is hamiltonian if α(G²) ≤ κ(G),... Read More about On hamiltonicity of P3-dominated graphs.

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.

Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult (2006)
Journal Article
Broersma, H., Fomin, F., Kratochvil, J., & Woeginger, G. (2006). Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult. Algorithmica, 44(4), 343-361. https://doi.org/10.1007/s00453-005-1176-8

We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a... Read More about Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult.

Global connectivity and expansion : long cycles and factors in f-connected graphs (2006)
Journal Article
Brandt, S., Broersma, H., Diestel, R., & Kriesell, M. (2006). Global connectivity and expansion : long cycles and factors in f-connected graphs. Combinatorica, 26(1), 17-36. https://doi.org/10.1007/s00493-006-0002-5

Given a function f : N → R, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k ≤ (n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expan... Read More about Global connectivity and expansion : long cycles and factors in f-connected graphs.

Radio labeling with preassigned frequencies (2004)
Journal Article
Bodlaender, H., Broersma, H., Fomin, F., Pyatkin, A., & Woeginger, G. (2004). Radio labeling with preassigned frequencies. SIAM Journal on Optimization, 15(1), 1-16. https://doi.org/10.1137/s1052623402410181

A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least $2$. The radio labeling problem (RL) consists in determining a radio labeling t... Read More about Radio labeling with preassigned frequencies.