No photo of Hajo Broersma

Hajo Broersma

prof.dr.ir.

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

Research Output 1987 2019

2013
17 Citations (Scopus)
9 Downloads (Pure)

Three complexity results on coloring $P_k$-free graphs

Broersma, H. J., Fomin, V. V., Golovach, P. A. & Paulusma, D., 2013, In : European journal of combinatorics. 34, 3, p. 609-619 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Colouring
Graph in graph theory
NP-complete problem
Imply
Vertex Coloring
4 Citations (Scopus)

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

Broersma, H. J., Golovach, P. A. & Patel, V., 2013, In : Theoretical computer science. 485, p. 69-84 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Toughness and vertex degrees

Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N. & Schmeichel, E., 2013, In : Journal of graph theory. 72, 2, p. 209-219 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

2012
6 Citations (Scopus)
18 Downloads (Pure)

Degree sequences and the existence of k-factors

Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N. & Schmeichel, E., Mar 2012, In : Graphs and combinatorics. 28, 2, p. 149-166 18 p.

Research output: Contribution to journalArticleAcademicpeer-review

File
21 Citations (Scopus)

Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time

Broersma, H. J., Golovach, P. A., Paulusma, D. & Song, J., 16 Mar 2012, In : Theoretical computer science. 423, p. 1-10 10 p.

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
42 Downloads (Pure)

How many conjectures can you stand: a survey

Broersma, H. J., Ryjáček, Z. & Vrána, P., 2012, In : Graphs and combinatorics. 28, 1, p. 57-75 19 p.

Research output: Contribution to journalArticleAcademicpeer-review

File
19 Citations (Scopus)
195 Downloads (Pure)

Max-plus algebraic throughput analysis of synchronous dataflow graphs

de Groote, R., Kuper, J., Broersma, H. J. & Smit, G. J. M., 2012, 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA). USA: IEEE Computer Society, p. 29-38 10 p.

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

File
28 Citations (Scopus)
1 Downloads (Pure)

Nascence project: nanoscale engineering for novel computation using evolution

Broersma, H. J., Gomez, F., Miller, J., Petty, M. & Tufte, G., 2012, In : International journal of unconventional computing. 8, 4, p. 313-317 5 p.

Research output: Contribution to journalArticleAcademic

1 Citation (Scopus)
28 Downloads (Pure)

Pairs of forbidden induced subgraphs for homogeneously traceable graphs

Li, B., Li, B., Broersma, H. J. & Zhang, S., Sep 2012, In : Discrete mathematics. 312, 18, p. 2800-2818 19 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
60 Downloads (Pure)

Subgraph conditions for Hamiltonian properties of graphs

Li, B. & Li, B., 20 Sep 2012, Enschede: Universiteit Twente. 221 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

File

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)
12 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

2 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)

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
6 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)
19 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

51 Downloads (Pure)

Removable Edges in 4-Connected Graphs

Wu, J., 2 Sep 2009, Zwolle: Wohrmann Printing Service. 130 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

File
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

16 Citations (Scopus)
1 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)

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., 10.1016/j.disc.2007.04.058.

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

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., 10.1016/j.disc.2007.11.026.

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
32 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
25 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)

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)
4 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)

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., 10.1016/j.disc.2005.11.049.

Research output: Contribution to journalArticleAcademicpeer-review

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)

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)

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

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)

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)
5 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
11 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