Broersma, H. J., Marchal, L., Paulusma, D., Salman, A. N. M.
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...
On hamiltonicity of $P_3$-dominated graphs (2009)
We introduce a new class of graphs which we call $P_3$-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let $G$ be a 2-connected...
Upper bounds and algorithms for parallel knock-out numbers (2009)
Broersma, H.J., Johnson, M., Paulusma, D.
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...
Complexity of conditional colorability of graphs (2009)
Li, X., Yao, X., Zhou, W., Broersma, H.J.
For positive integers $k$ and $r$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to...
Broersma, H.J., Marchal, L., Paulusma, D., Salman, A.N.M.
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...
Dirac's minimum degree condition (2008)
H. J. Broersma, Grundlagen Der Informatik, Tu Cottbus
restricted to claws
Computing sharp 2-factors in claw-free graphs (2008)
In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many...
Connected even factors in claw-free graphs (2008)
Li, M.C., Xiong, L., Broersma, H.J.
A connected even $[2,2s]$-factor of a graph $G$ is a connected factor with all vertices of degree $i(i=2,4,\ldots,2s)$, where $s\ge 1$ is an integer. In this paper, we show that every supereulerian...
A new algorithm for on-line coloring bipartite graphs (2008)
Broersma, H.J., Capponi, A., Paulusma, D.
We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of...
The computational complexity of the parallel knock-out problem (2008)
Broersma, H.J., Johnson, M., Paulusma, D., Stewart, I.A.
We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its...
Some families of integral graphs (2008)
Wang, L., Broersma, H.J., Hoede, C., Li, X., Still, G.J.
A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs $K_{1,r}\cdot K_n,\; r^*K_n,\; K_{1,r} \cdot K_{m,n},\; r^*K_{m,n}$ and the tree...
Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks (2008)
Broersma, H.J., Fijavz, G., Kaiser, T., Kuzel, R., Ryjácek, Z., Vrána, P.
We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically...
A New Upper Bound on the Cyclic Chromatic Number (2007)
O. V. Borodin, H. J. Broersma, A. Glebov
A cyclic colouring of a plane graph is a vertex colouring such that vertices incident with the same face have distinct colours. The minimum number of colours in a cyclic colouring of a graph is its...
Backbone colorings for graphs: Tree and path backbones (2007)
Broersma, H.J., Fomin, F.V., Golovach, P.A., Woeginger, G.J.
We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$...
Tutte sets in graphs I: Maximal tutte sets and D-graphs (2007)
Bauer, D., Broersma, H.J., Morgana, A., Schmeichel, E.
A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of what is usually called the deficiency of $G$. A subset $X$ of $V(G)$ for which this...
On Ramsey numbers for paths versus wheels (2007)
Salman, A.N.M., Broersma, H.J.
For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a...
Tutte sets in graphs II: The complexity of finding maximum Tutte sets (2007)
Bauer, D., Broersma, H.J., Kahl, N., Morgana, A., Schmeichel, E., Surowiec, T.
A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of what is usually called the deficiency. A subset $X$ of $V(G)$ for which this deficiency is...
Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks (2007)
Broersma, H.J., Fijavž, G., Kaiser, T., Kužel, R., Ryjáček, Z., Vrána, P.
We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is hamiltonian), by Thomassen (every 4-connected line graph is hamiltonian) and by Fleischner (every cyclically...
Integral trees of diameter 6 (2007)
Wang, L., Broersma, H.J., Hoede, C., Li, X., Still, G.J.
A graph $G$ is called integral if all eigenvalues of its adjacency matrix $A(G)$ are integers. In this paper, the trees $T(p,q)\cdot T(r,m,t)$ and $K_{1,s}\cdot T(p,q)\cdot T(r,m,t)$ of diameter 6...
Path–kipas Ramsey numbers (2007)
Salman, A.N.M., Broersma, H.J.
For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a...
Improved upper bounds for $\lambda$-backbone colorings along matchings and stars (2007)
Broersma, H.J., Marchal, L., Paulusma, D., Salman, A.N.M.
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...
On the complexity of dominating set problems related to the minimum all-ones problem (2007)
The minimum all-ones problem and the connected odd dominating set problem were shown to be NP-complete in different papers for general graphs, while they are solvable in linear time (or trivial) for...
Upper bounds and algorithms for parallel knock-out numbers (2007)
Broersma, H.J., Johnson, M., Paulusma, D.
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...
On components of 2-factors in claw-free graphs (2007)
Broersma, H.J., Paulusma, D., Yoshimoto, K.
For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. If $\delta=4$, then $G$ has a 2-factor with at most $(5n-14)/18$ components, unless $G$...
Toughness and hamiltonicity in k-trees (2007)
Broersma, H.J., Xiong, L., Yoshimoto, K.
We consider toughness conditions that guarantee the existence of a hamiltonian cycle in $k$-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are...
Eliminating graphs by means of parallel knock-out schemes (2007)
Broersma, H.J., Fomin, F.V., Královič, R., Woeginger, G.J.
In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one...
Subpancyclicity of line graphs and degree sums along paths (2006)
A graph is called subpancyclic if it contains a cycle of length $\ell$ for each $\ell$ between 3 and the circumference of the graph. We show that if $G$ is a connected graph on $n\ge 146$ vertices...
Path-fan Ramsey numbers (2006)
Salman, A.N.M., Broersma, H.J.
For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a...
On-line coloring of H-free bipartite graphs (2006)
Broersma, H.J., Capponi, A., Paulusma, D.
We present a new on-line algorithm for coloring bipartite graphs. This yields a new upper bound on the on-line chromatic number of bipartite graphs, improving a bound due to Lovasz, Saks and Trotter....
Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult (2006)
Broersma, H.J., Fomin, F.V., Kratochvil, J., Woeginger, G.J.
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...
The Computational Complexity of the Parallel Knock-Out Problem (2006)
Broersma, H.J., Johnson, M., Paulusma, D., Stewart, I.A.
We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its...
Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs (2006)
Brandt, S., Broersma, H.J., Diestel, R., Kriesell, M.
Given a function $f: {\mathbb N}\to{\mathbb R}$, call an $n$-vertex graph $f$-connected if separating off $k$ vertices requires the deletion of at least $f(k)$ vertices whenever $k\le (n−f(k))/2$....
Toughness in graphs - A survey (2006)
Bauer, D., Broersma, H.J., Schmeichel, E.
In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology...
A new upper bound on the cyclic chromatic number (2006)
Borodin, O.V., Broersma, H.J., Glebov, A.
A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic...
The computational complexity of the minimum weight processor assignment problem (2005)
Broersma, H.J., Paulusma, D., Smit, G.J.M., Vlaardingerbroek, F., Woeginger, G.J.
In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors. This should be donein an energy-effcient way. We give the background of the...
A new upper bound on the cyclic chromatic number (2004)
Borodin, O. V., Broersma, H. J., Glebov, A., Van Den Heuvel, Jan
A cyclic colouring of a plane graph is a vertex colouring such that vertices incident with the same face have distinct colours. The minimum number of colours in a cyclic colouring of a graph is its...
On Ramsey numbers for paths versus wheels (2004)
Salman, A.N.M., Broersma, H.J.
For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a...
Path-kipas Ramsey numbers (2004)
Salman, A.N.M., Broersma, H.J.
For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a...
A continuation of spanning 2-connected subgraphs in truncated rectangular grid graphs (2003)
Salman, A.N.M., Broersma, H.J., Rodger, C.A.
A grid graph is a finite induced subgraph of the infinite 2-dimensi-onal grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. An...
Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult (2003)
Broersma, H.J., Fomin, F.V., Kratochvil, J., Woeginger, G.J.
We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the...
More on spanning 2-connected subgraphs of alphabet graphs, special classes of grid graphs (2003)
Salman, A.N.M., Broersma, H.J., Rodger, C.A.
A grid graph $G$ is a finite induced subgraph of the infinite 2-dimensional grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. A...
Path-fan Ramsey numbers (2003)
Salman, A.N.M., Broersma, H.J.
For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a...
A general framework for coloring problems: old results, new results, and open problems (2003)
In this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of...
Backbone colorings for networks: tree and path backbones (2003)
Broersma, H.J., Fomin, F.V., Golovach, P.A., Woeginger, G.J.
We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$ and...
Backbone colorings along perfect matchings (2003)
Broersma, H.J., Fujisawa, J., Yoshimoto, K.
Given a graph $G=(V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$ and $H$ is a proper vertex coloring $V\rightarrow \{1,2,\ldots\}$ of $G$ in which the...
The Ramsey numbers of large star-like trees versus large odd wheels (2002)
For two given graphs $G$ and $H$, the \textit{Ramsey number} $R(G,H)$ is the smallest positive integer $N$ such that for every graph $F$ of order $N$ the following holds: either $F$ contains $G$ as a...
On stability of the Hamiltonian index under contractions and closures (2002)
Xiong, L., Ryjáček, Z., Broersma, H.J.
The hamiltonian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is hamiltonian. We first show that, with one exceptional case, adding an edge to a...
Spanning 2-connected subgraphs of alphabet graphs, special classes of grid graphs (2002)
Salman, A.N.M., Baskoro, E.T., Broersma, H.J.
A grid graph $G$ is a finite induced subgraph of the infinite 2-dimensional grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. A...
Spanning 2-connected subgraphs in truncated rectangular grid graphs (2002)
Salman, A.N.M., Baskoro, E.T., Broersma, H.J.
A grid graph is a finite induced subgraph of the infinite 2-dimensio- nal grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. An...
Stars and bunches in planar graphs. Part I: Triangulations (2002)
Borodin, O.V., Broersma, H.J., Glebov, A.
Given a plane graph, a $k$-star at $u$ is a set of $k$ vertices with a common neighbour $u$; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have...
Stars and bunches in planar graphs. Part II: General planar graphs and colourings (2002)
Borodin, O.V., Broersma, H.J., Glebov, A.
Given a plane graph, a $k$-star at $u$ is a set of $k$ vertices with a common neighbour $u$; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have...
The Ramsey numbers of large cycles versus small wheels (2002)
For two given graphs $G$ and $H$, the \textit{Ramsey number} $R(G,H)$ is the smallest positive integer $N$ such that for every graph $F$ of order $N$ the following holds: either $F$ contains $G$ as a...
More about subcolorings (2002)
Broersma, H.J., Fomin, F.V., Nešetřil, J., Woeginger, G.J.
A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity...
Radio labeling with pre-assigned frequencies (2002)
Bodlaender, H.L., Broersma, H.J., Fomin, F.V., Pyatkin, A.V., Woeginger, G.J.
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...
More on spanning 2-connected subgraphs in truncated rectangular grid graphs (2002)
Salman, A.N.M., Baskoro, E.T., Broersma, H.J.
A grid graph is a finite induced subgraph of the infinite 2-dimensional grid defined by $Z \times Z$ and all edges between pairs of vertices from $Z \times Z$ at Euclidean distance precisely 1. An...
Toughness and hamiltonicity in $k$-trees (2001)
Broersma, H.J., Xiong, L., Yoshimoto, K.
We consider toughness conditions that guarantee the existence of a hamiltonian cycle in $k$-trees, a subclass of the class of chordal graphs. By a result of Chen et al.\ 18-tough chordal graphs are...
Subpancyclicity in the line graph of a graph with large degree sums of vertices along a path (2001)
Xiong, L., Broersma, H.J., Hoede, C.
A graph is called {\sl subpancyclic} if it contains a cycle of length $l$ for each $l$ between 3 and the circumference of a graph. We show that if $G$ is a connected graph on $n\geq 146$ vertices...
The Hamiltonian index of a graph and its branch-bonds (2001)
Xiong, L., Broersma, H.J., Li, X.
Let $G$ be an undirected and loopless finite graph that is not a path. The minimum $m$ such that the iterated line graph $L^m(G)$ is hamiltonian is called the hamiltonian index of $G,$ denoted by...
Strengthening the closure concept in claw-free graphs (2000)
We give a strengthening of the closure concept for claw-free graphs introduced by the second author in 1997. The new closure of a claw-free graph $G$ defined here is uniquely determined and preserves...
A fan type condition for heavy cycles in weighted graphs (2000)
Broersma, H.J., Zhang, Shenggui, Li, X., Wang, L.
A weighted graph is a graph in which each edge $e$ is assigned a non-negative number $w(e)$, called the weight of $e$. The weight of a cycle is the sum of the weights of its edges. The weighted...
A $\sigma_3$ type condition for heavy cycles in weighted graphs (2000)
Broersma, H.J., Zhang, Shenggui, Li, X.
A weighted graph is a graph in which each edge $e$ is assigned a non-negative number $w(e)$, called the weight of $e$. The weight of a cycle is the sum of the weights of its edges. The weighted...
More progress on tough graphs -- The Y2K report (2000)
Bauer, D., Broersma, H.J., Schmeichel, E.
We now know that not every $2$-tough graph is hamiltonian. In fact for every $\epsilon > 0$, there exists a ($9/4 - \epsilon$) - tough nontraceable graph. We continue our quadrennial survey of...
Directed paths with few or many colors in colored directed graphs (2000)
Li, X., Zhang, Shenggui, Broersma, H.J.
Given a graph $D=(V(D),A(D))$ and a coloring of $D$, not necessarily a proper coloring of either the arcs or the vertices of $D$, we consider the complexity of finding a path of $D$ from a given...
On factors of 4-connected claw-free graphs (1999)
We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of...
Forbidden subgraphs that imply Hamiltonian-connectedness (1999)
Broersma, H.J., Faudree, R.J., Huck, A., Trommel, H., Veldman, H.J.
It is proven that if $G$ is a $3$-connected claw-free graph which is also $Z_3$-free (where $Z_3$ is a triangle with a path of length $3$ attached), $P_6$-free (where $P_6$ is a path with $6$...
Throughput of ADSL modems (1999)
Broersma, H.J., Bruin, N., Hurink, J.L., Meester, L.E., Op De Beek, S.S., Westhuis, J.
This paper considers the throughput of ADSL (Asymmetric Digital Subscriber Line) modems, used for high-speed data transmission over relatively unreliable connections, e.g. copper telephone wires. The...
On factors of 4-connected claw-free graphs (1999)
Broersma, H.J., Kriesell, M., Ryjáček, Z.
We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of...
Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion (1999)
Bauer, D., Broersma, H.J., Morgana, A., Schmeichel, E.
A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and...
On minimum degree conditions for supereulerian graphs (1999)
A graph is called supereulerian if it has a spanning closed trail. Let $G$ be a 2-edge-connected graph of order $n$ such that each minimal edge cut $E \subseteq E (G)$ with $|E| \le 3$ satisfies the...
On some intriguing problems in Hamiltonian graph theory -- A survey (1999)
We survey results and open problems in Hamiltonian graph theory centred around three themes: regular graphs, $t$-tough graphs, and claw-free graphs.
Isomorphisms and traversability of directed path graphs (1998)
The concept of a line digraph is generalized to that of a directed path graph. The directed path graph !Pk(D) of a digraph D is obtained by representing the directed paths on k vertices of D by...
Various results on the toughness of graphs (1998)
H. J. Broersma, E. A. Engbers, H. Trommel, Hajo Broersma, Erik Engbers, Huib Trommel
Let G be a graph, and let t ≥ 0 be a real number. Then G is t-tough if tω(G − S) ≤|S| for all S ⊆ V (G) with ω(G − S)> 1, where ω(G − S) denotes the number of components of G − S....
Republic of China HEAVY PATHS AND CYCLES IN WEIGHTED GRAPHS ∗ (1998)
S. Zhang, X. Li, H. J. Broersma, Shenggui Zhang, Xueliang Li, Hajo Broersma
A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. In this paper, some theorems on the existence of long paths and cycles in unweighted...
Heavy paths and cycles in weighted graphs (1998)
Zhang, Shenggui, Li, X., Broersma, H.J.
A weighted graph is a graph in which each edge $e$ is assigned a non-negative number $w(e)$, called the weight of $e$. In this paper, some theorems on the existence of long paths and cycles in...
Some approaches to a conjecture on short cycles in digraphs (1998)
We consider the following special case of a conjecture due to Caccetta and H\"aggkvist: Let $D$ be a digraph on $n$ vertices that all have in-degree and out-degree at least $n/3$. Then $D$ contains a...
Various results on the toughness of graphs (1997)
Broersma, H.J., Engbers, E.A., Trommel, H.
Let G be a graph, and let t 0 be a real number. Then G is t-tough if t!(G − S) jSj for all S V (G) with !(G − S) > 1, where !(G − S) denotes the number of components of G − S. The toughness...
The concept of a line digraph is generalized to that of a directed path graph. The directed path graph !Pk(D) of a digraph D is obtained by representing the directed paths on k vertices of D by...
I.: Unifying results on hamiltonian clawfree graphs (1994)
H. J. Broersma, I. Schiermeyer
This work was motivated by many (recent) papers on hamiltonicity of claw-free graphs, i.e. graphs that do not contain K 1;3 as an induced subgraph. By combining ideas from these papers with some new...
I.: Toughness and hamiltonicity in almost claw-free graphs. Memorandum 1114, Univ. of Twente (1993)
H. J. Broersma, I. Schiermeyer
Some known results on claw-free (K 1;3-free) graphs are generalized to the larger class of almost claw-free graphs which were introduced by Ryj'acek. In particular, we show that a 2-connected...
On “The matching polynomial of a polygraph” (1993)
In this note we give an explanation for two phenomena mentioned in the concluding remarks of “The matching polynomial of a polygraph ” by Babic et al. The following results are ob-tained: (1)...
H. J. Broersma, I. Schiermeyerb
Closure theorems in hamiltonian graph theory are of the following type: Let G be a 2-connected graph and let II, u be two distinct nonadjacent vertices of G. If condition c(u, u) holds, then G is...