Hajo Broersma

prof.dr.ir.

1987 …2019
If you made any changes in Pure these will be visible here soon.

Research Output 1987 2019

2012
6 Downloads (Pure)

The complexity of finding uniform sparsest cuts in various graph classes

Bonsma, P. S., Broersma, H. J., Patel, V. & Pyatkin, A. V., 2012, In : Journal of discrete algorithms. 14, p. 136-149 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Graph Classes
Computational complexity
Polynomials
Decomposition
Graph in graph theory
3 Citations (Scopus)
17 Downloads (Pure)

Tight complexity bounds for FPT subgraph problems parameterized by clique-width

Broersma, H. J., Golovach, P. A. & Patel, V., 2012, Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. Marx, D. & Rossmanith, P. (eds.). London: Springer, p. 207-218 12 p. (Lecture Notes in Computer Science; vol. 7112).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

File
Clique-width
Subgraph
Induced Subgraph
Exponential time
Minimum Degree
34 Citations (Scopus)

Updating the complexity status of coloring graphs without a fixed induced linear forest

Broersma, H. J., Golovach, P. A., Paulusma, D. & Song, J., 13 Jan 2012, In : Theoretical computer science. 414, 1, p. 9-19 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

2011
4 Citations (Scopus)

Hamiltonian connectedness in 4-connected hourglass-free claw-free graphs

Li, M., Chen, X. & Broersma, H. J., Dec 2011, In : Journal of graph theory. 68, 4, p. 285-298 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

The complexity status of problems related to sparsest cuts

Bonsma, P. S., Broersma, H. J., Patel, V. & Pyatkin, A., Mar 2011, Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010. Iliopoulos, C. S. & Smyth, W. F. (eds.). Berlin, Heidelberg: Springer, p. 125-135 11 p. (Lecture Notes in Computer Science; vol. 6460).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2010
3 Citations (Scopus)
11 Downloads (Pure)

Computing sharp 2-factors in claw-free graphs

Broersma, H. J. & Paulusma, D., Sep 2010, In : Journal of discrete algorithms. 8, 3, p. 321-329 9 p., 10.1016/j.jda.2009.07.001.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Claw-free Graphs
Byproducts
Computing
Number of Components
Polynomials
7 Citations (Scopus)

Fast exact algorithms for hamiltonicity in claw-free graphs

Broersma, H. J., Fomin, F. V., van 't Hof, P. & Paulusma, D., Feb 2010, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers. Paul, C. & Habib, M. (eds.). Berlin: Springer, p. 44-53 10 p. (Lecture Notes in Computer Science; vol. 5911).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Hamiltonicity
Claw-free Graphs
Hamiltonian circuit
Exact Algorithms
Fast Algorithm
2009
9 Citations (Scopus)
30 Downloads (Pure)

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

Broersma, H. J., Marchal, B., Paulusma, D. & Salman, M., Mar 2009, In : Discussiones mathematicae. Graph theory. 29, 1, p. 143-162 20 p.

Research output: Contribution to journalArticleAcademicpeer-review

File
15 Citations (Scopus)

Complexity of conditional colorability of graphs

Li, X., Li, X., Yao, X., Zhou, W. & Broersma, H. J., Mar 2009, In : Applied mathematics letters. 22, 3, p. 320-324 5 p.

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Fully decomposable split graphs

Broersma, H. J., Kratsch, D. & Woeginger, G., 2009, Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009. Fiala, J., Kratochvil, J. & Miller, M. (eds.). Berlin: Springer, p. 105-112 8 p. 10.1007/978-3-642-10217-2_13. (Lecture Notes in Computer Science; vol. 5874).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

On hamiltonicity of P3-dominated graphs

Broersma, H. J. & Vumar, E., May 2009, In : Mathematical methods of operations research. 69, 2, p. 297-306 10 p., 10.1007/s00186-008-0260-7.

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs

Broersma, H. J., Paulusma, D. & Yoshimoto, K., 2009, In : Graphs and combinatorics. 25, 4, p. 427-460 34 p., 10.1007/s00373-009-0855-7.

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

Three Complexity Results on Coloring $P_k$-Free Graphs

Broersma, H. J., Fomin, F. V., Golovach, P. A. & Paulusma, D., 2009, Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009. Fiala, J., Kratochvil, J. & Miller, M. (eds.). Berlin: Springer, p. 95-104 10 p. 10.1007/978-3-642-10217-2_12. (Lecture Notes in Computer Science; vol. 5874).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Upper bounds and algorithms for parallel knock-out numbers

Broersma, H. J., Johnson, M., Paulusma, D. & Stewart, I. A., Mar 2009, In : Theoretical computer science. 410, 14, p. 1319-1327 9 p., 10.1016/j.tcs.2008.03.024.

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
10 Downloads (Pure)

λ-backbone colorings along pairwise disjoint stars and matchings

Broersma, H. J., Fujisawa, J., Marchal, L., Paulusma, D., Salman, M. & Yoshimoto, K., 28 Sep 2009, In : Discrete mathematics. 309, 18, p. 5596-5609 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
2008
13 Citations (Scopus)

A new algorithm for on-line coloring bipartite graphs

Broersma, H. J., Capponi, A. & Paulusma, D., Feb 2008, In : SIAM journal on discrete mathematics. 22, WoTUG-31/1, p. 72-91 20 p., 10.1137/060668675.

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Computing sharp 2-factors in claw-free graphs

Broersma, H. J. & Paulusma, D., Aug 2008, 33rd International Symposium on Mathematical Foundations of Computer Science. Berlin: Springer, p. 193-204 12 p. 10.1007/978-3-540-85238-4_15. (Lecture Notes in Computer Science; vol. 5162, no. WoTUG-31).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
12 Downloads (Pure)

Connected even factors in claw-free graphs

Li, M. C., Xiong, L. & Broersma, H. J., Jun 2008, In : Discrete mathematics. 308, WoTUG-31/11, p. 2282-2284 3 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
11 Citations (Scopus)
10 Downloads (Pure)

Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks

Broersma, H. J., Fijavz, G., Kaiser, T., Kuzel, R., Ryjacek, Z. & Vrana, P., Dec 2008, In : Discrete mathematics. 308, WoTUG-31/24, p. 6064-6077 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
3 Citations (Scopus)
43 Downloads (Pure)

Some families of integral graphs

Wang, L., Broersma, H. J., Hoede, C., Li, X., Li, X. & Still, G. J., Dec 2008, In : Discrete mathematics. 308, WoTUG-31/24, p. 6383-6391 9 p., 10.1016/j.disc.2007.12.010.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Integral Graphs
Number theory
Polynomials
Graph in graph theory
K-tree
5 Citations (Scopus)

The computational complexity of the parallel knock-out problem

Broersma, H. J., Johnson, M., Paulusma, D. & Stewart, I. A., Mar 2008, In : Theoretical computer science. 393, 1-3, p. 182-195 14 p., 10.1016/j.tcs.2007.11.021.

Research output: Contribution to journalArticleAcademicpeer-review

2007
26 Citations (Scopus)

Backbone colorings for graphs: Tree and path backbones

Broersma, H. J., Fomin, F. V., Golovach, P. A. & Woeginger, G., Jan 2007, In : Journal of graph theory. 55, SINTEF A13/2, p. 137-152 16 p., 10.1002/jgt.20228.

Research output: Contribution to journalArticleAcademicpeer-review

Contractible subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for snarks

Broersma, H. J., Fijavz, G., Kaiser, T., Kuzel, R., Ryjacek, Z. & Vrana, P., 1 Mar 2007, In : Electronic notes in discrete mathematics. 28, 4542, p. 55-59 5 p., 10.1016/j.endm.2007.01.009.

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
10 Downloads (Pure)

Eliminating graphs by means of parallel knock-out schemes

Broersma, H. J., Fomin, F. V., Královič, R. & Woeginger, G., Jan 2007, In : Discrete applied mathematics. 155, 1/2, p. 92-102 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Hamiltonians
Dynamic programming
Polynomials
Graph in graph theory
Claw-free Graphs
5 Citations (Scopus)

Improved upper bounds for λ-backbone colorings along matchings and stars

Broersma, H. J., Marchal, L., Paulusma, D. & Salman, M., 13 Jul 2007, Proceedings of SOFSEM 2007: Theory and Practice of Computer Science. van Leeuwen, J., Italiano, G. F., van der Hoek, W., Meinel, C., Sack, H. & Plásil, F. (eds.). Berlin: Springer, p. 188-199 12 p. 10.1007/978-3-540-69507-3. (Lecture Notes in Computer Science; vol. 4362, no. LNCS4549).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
10 Downloads (Pure)

Integral trees of diameter 6

Wang, L., Broersma, H. J., Hoede, C., Li, X., Li, X. & Still, G. J., 15 May 2007, In : Discrete applied mathematics. 155, 4542/10, p. 1254-1266 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Number theory
Polynomials
Diophantine equation
Characteristic polynomial
Adjacency Matrix

On components of 2-factors in claw-free graphs

Broersma, H. J., Paulusma, D. & Yoshimoto, K., Aug 2007, EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications. Amsterdam: Elsevier, p. 289-293 5 p. 10.1016/j.endm.2007.07.050. (Electronic Notes in Discrete Mathematics; vol. 29, no. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
8 Downloads (Pure)

On Ramsey numbers for paths versus wheels

Salman, M. & Broersma, H. J., 6 Apr 2007, In : Discrete mathematics. 307, D-07-01/7-8, p. 975-982 8 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
1 Citation (Scopus)

On the complexity of dominating set problems related to the minimum all-ones problem

Broersma, H. J., Li, X. & Li, X., Oct 2007, In : Theoretical computer science. 385, 1/1-3, p. 60-70 11 p., 10.1016/j.tcs.2007.05.027.

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
8 Downloads (Pure)

Path-kipas Ramsey numbers

Salman, M. & Broersma, H. J., 1 Sep 2007, In : Discrete applied mathematics. 155, LNCS4549/14, p. 1878-1884 7 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Ramsey number
Path
Subgraph
Graph in graph theory
Odd
7 Citations (Scopus)
8 Downloads (Pure)

Toughness and hamiltonicity in k-trees

Broersma, H. J., Xiong, L. & Yoshimoto, K., 6 Apr 2007, In : Discrete mathematics. 307, 1/7-8, p. 832-838 7 p., 10.1016/j.disc.2005.11.051.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
4 Citations (Scopus)

Tutte sets in graphs I: Maximal tutte sets and D-graphs

Bauer, D., Broersma, H. J., Morgana, A. & Schmeichel, E., Mar 2007, In : Journal of graph theory. 55, SINTEF A13/4, p. 343-358 16 p., 10.1002/jgt.20243.

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
11 Downloads (Pure)

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

Bauer, D., Broersma, H. J., Kahl, N., Morgana, A., Schmeichel, E. & Surowiec, T., 15 May 2007, In : Discrete applied mathematics. 155, 4542/10, p. 1336-1343 8 p., 10.1016/j.dam.2007.02.002.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Polynomials
Graph in graph theory
Maximum Matching
Algorithmic Complexity
Polynomial Algorithm
1 Citation (Scopus)

Upper bounds and algorithms for parallel knock-out numbers

Broersma, H. J., Johnson, M. & Paulusma, D., Jul 2007, SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity. Prencipe, G. & Zaks, S. (eds.). Berlin: Springer, p. 328-340 13 p. 10.1007/978-3-540-72951-8_26. (Lecture Notes in Computer Science; vol. 4474, no. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2006
4 Citations (Scopus)

A new upper bound on the cyclic chromatic number

Borodin, O. V., Broersma, H. J., Glebov, A. & van den Heuvel, J., 2006, In : Journal of graph theory. 54, suppl 2/1, p. 58-72 15 p., 10.1002/jgt.20193.

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Brandt, S., Broersma, H. J., Diestel, R., Kriesell, M. & Kriesell, M., Feb 2006, In : Combinatorica. 26, 06EX1521/1, p. 17-36 20 p.

Research output: Contribution to journalArticleAcademicpeer-review

Long Cycle
Connected graph
Connectivity
Vertex Connectivity
Hamiltonicity
4 Citations (Scopus)

On-line coloring of H-free bipartite graphs

Broersma, H. J., Capponi, A. & Paulusma, D., 2006, Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. Calamoneri, T., Finocchi, I. & Italiano, G. F. (eds.). Berlin, Heidelberg: Springer, p. 284-295 12 p. (Lecture Notes in Computer Science; vol. 3998).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Bipartite Graph
Colouring
Chromatic number
Upper bound
Path
12 Citations (Scopus)
15 Downloads (Pure)

Path-fan Ramsey numbers

Salman, M. & Broersma, H. J., Feb 2006, In : Discrete applied mathematics. 154, 06EX1521/9, p. 1429-1436 8 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Ramsey number
Fans
Path
Subgraph
Triangle
12 Citations (Scopus)

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

Broersma, H. J., Fomin, F. V., Kratochvil, J. & Woeginger, G., May 2006, In : Algorithmica. 44, 4, p. 343-361 19 p., 10.1007/s00453-005-1176-8.

Research output: Contribution to journalArticleAcademicpeer-review

5 Downloads (Pure)

Subpancyclicity of line graphs and degree sums along paths

Xiong, L. & Broersma, H. J., 2 Jun 2006, In : Discrete applied mathematics. 154, 06EX1521/9, p. 1453-1463 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Degree Sum
Hamiltonians
Line Graph
Path
Graph in graph theory
1 Citation (Scopus)

The Computational Complexity of the Parallel Knock-Out Problem

Broersma, H. J., Johnson, M., Paulusma, D. & Stewart, I. A., 2006, Proceedings of the 7th Latin American Symposium (LATIN 2006). Correa, J. R., Hevia, A. & Kiwi, M. (eds.). Berlin: Springer, p. 250-261 12 p. 10.1007/11682462_26. (Lecture Notes in Computer Science; vol. 3887, no. 11).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

53 Citations (Scopus)

Toughness in graphs - A survey

Bauer, D., Broersma, H. J. & Schmeichel, E., Apr 2006, In : Graphs and combinatorics. 22, 10/1, p. 1-35 35 p., 10.1007/s00373-006-0649-0.

Research output: Contribution to journalArticleAcademicpeer-review

2005
6 Citations (Scopus)

A General Framework for Coloring Problems: Old Results, New Results, and Open Problems

Broersma, H., 2005, Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. Akiyama, J., Baskoro, E. T. & Kano, M. (eds.). Berlin: Springer, p. 65-79 14 p. (Lecture Notes in Computer Science; vol. 3330).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Colouring
Open Problems
Frequency Assignment
Biased
Framework
7 Citations (Scopus)

An Upper Bound for the Ramsey Number of a Cycle of Length Four Versus Wheels

Surahmat, Baskoro, E. T., Uttunggadewa, S. & Broersma, H., 2005, Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. Akiyama, J., Baskoro, E. T. & Kano, M. (eds.). Berlin: Springer, p. 181-184 3 p. (Lecture Notes in Computer Science; vol. 3330).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Ramsey number
Wheel
Upper bound
Cycle
Graph in graph theory
30 Downloads (Pure)

Handelsreizigers in wiskunde : promotionele activiteiten op de Universiteit Twente

Broersma, H. J. & Ruizenaar, H. W. A., 2005, In : Nieuw archief voor wiskunde. Ser. 5, vol. 6, 2, p. 153-155

Research output: Contribution to journalArticleAcademic

File
3 Citations (Scopus)
58 Downloads (Pure)

Mapping applications to a coarse grain reconfigurable system

Guo, Y., Smit, G. J. M., Broersma, H. J., Rosien, M. A. J., Heysters, P. M. & Krol, T., Jul 2005, New Algorithms, Architectures and Applications for Reconfigurable Computing. Lysaght, P. & Rosenstiel, W. (eds.). Dordrecht: Kluwer Academic Publishers, p. 93-104 12 p.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

File

More on spanning 2-connected subgraphs of alphabet graphs, special classes of grid graphs

Salman, M., Broersma, H. J. & Rodger, C. A., 2005, In : Bulletin of the Institute of Combinatorics and its Applications. 45, p. 17-32 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

On stability of the Hamiltonian index under contractions and closures

Broersma, H. J., Xiong, L. & Ryjácek, Z., 2005, In : Journal of graph theory. 49, p. 104-115 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

57 Citations (Scopus)
54 Downloads (Pure)

Paths and cycles in colored graphs

Broersma, H. J., Li, X., Li, X., Woeginger, G. & Zhang, S., 2005, In : Australasian journal of combinatorics. 31, 1, p. 299-311 12 p.

Research output: Contribution to journalArticleAcademicpeer-review

File
49 Downloads (Pure)

The Ramsey number of fans versus K4

Surahmat, Baskoro, E. T. & Broersma, H. J., 2005, In : Bulletin of the Institute of Combinatorics and its Applications. 43, p. 96-102 6 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File