Recent publications


  The following links are selfexplanatory:

  Papers in 2010
  Papers in 2009
  Papers in 2008
  Papers in 2007
  Papers in 2006
  Papers in 2005
  Papers in 2004
  Papers in 2003



Conference and Journal papers in 2010


  1. H.J. Broersma and D. Paulusma, Computing sharp 2-factors in claw-free graphs, Journal of Discrete Algorithms 8 (2010) 321-329 DOI link to paper.
  2. H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma, Fast exact algorithms for hamiltonicity in claw-free graphs, Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, June 24-26, 2009, Lecture Notes in Computer Science 5911 (2010) 44-53 DOI link to paper.
  3. H.J. Broersma, P.A. Golovach, D. Paulusma and J. Song, Narrowing down the gap on the complexity of coloring Pk-free graphs, accepted for WG 2010.
  4. P. Bonsma, H.J. Broersma, V. Patel and A. Pyatkin, The complexity status of problems related to sparsest cuts, accepted for IWOCA 2010.

Conference and Journal papers in 2009


  1. H.J. Broersma and D. Paulusma, Computing sharp 2-factors in claw-free graphs, to appear in Journal of Discrete Algorithms DOI link to paper.
  2. H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto, l-Backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics 309 (2009) 5596-5609 DOI link to paper.
  3. H.J. Broersma and E. Vumar, On hamiltonicity of P3-dominated graphs, Mathematical Methods of Operations Research 69 (2009) 297-306 DOI link to paper.
  4. H.J. Broersma, D. Kratsch and G.J. Woeginger, Fully decomposable split graphs, accepted for IWOCA 2009, published in Lecture Notes in Computer Science 5874 (2009) 4105-112 DOI link to paper.
  5. H.J. Broersma, F.V. Fomin, P.A. Golovach and D. Paulusma, Three complexity results on coloring Pk-free graphs, accepted for IWOCA 2009, published in Lecture Notes in Computer Science 5874 (2009) 495-104 DOI link to paper.
  6. H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma, Fast exact algorithms for hamiltonicity in claw-free graphs, accepted for WG 2009 list of accepted papers.
  7. H.J. Broersma, D. Paulusma and K. Yoshimoto, Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs, Graphs and Combinatorics 25 (2009) 427-460. DOI link to paper.
  8. Xueliang Li, Xiangmei Yao, Wenli Zhou and H.J. Broersma, Complexity of conditional colorability of graphs, Applied Mathematics Letters 22 (2009) 320-324 DOI link to paper.
  9. H.J. Broersma, M. Johnson and D. Paulusma, Upper bounds and algorithms for parallel knock-out numbers, Theoretical Computer Science 410 (2009) 1319-1327. DOI link to paper.
  10. H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman, Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number, Discussiones Mathematicae Graph Theory 29 (2009) 143-162. link to paper.

Conference and Journal papers in 2008


  1. H.J. Broersma and E. Vumar, On hamiltonicity of P3-dominated graphs, Mathematical Methods of Operations Research (in press) DOI link to paper.
  2. H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman, Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number, to appear in Discussiones Mathematicae Graph Theory.
  3. H.J. Broersma and D. Paulusma, Computing sharp 2-factors in claw-free graphs, accepted for MFCS 2008: 33rd International Symposium on Mathematical Foundations of Computer Science, August 27-31, 2008, Torun, Poland list of accepted papers; Lecture Notes in Computer Science 5162 (2008) 193-204. DOI link to paper.
  4. Xueliang Li, Xiangmei Yao, Wenli Zhou and H.J. Broersma, Complexity of conditional colorability of graphs, Applied Mathematics Letters (in press) DOI link to paper.
  5. H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto, l-Backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics (in press) DOI link to paper.
  6. H.J. Broersma, M. Johnson and D. Paulusma, Upper bounds and algorithms for parallel knock-out numbers, Theoretical Computer Science (in press) DOI link to paper.
  7. H.J. Broersma, G. Fijavz, T. Kaiser, R. Kuzel, Z. Ryjacek and P. Vrana, "Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks", Discrete Mathematics 308 (2008) 6064-6077. DOI link to paper.
  8. Ligong Wang, H.J. Broersma, C. Hoede, Xueliang Li and G. Still, Some families of integral graphs, Discrete Mathematics 308 (2008) 6383-6391. DOI link to paper.
  9. MingChu Li, Liming Xiong, H.J. Broersma, Connected even factors in claw-free graphs, Discrete Mathematics 308 (2008) 2282-2284. DOI link to paper.
  10. H.J. Broersma, A. Capponi and D. Paulusma, A new algorithm for on-line coloring bipartite graphs, SIAM Journal on Discrete Mathematics 22 (2008) 72-91. DOI link to paper.
  11. H.J. Broersma, M. Johnson, D. Paulusma and I.A. Stewart, The computational complexity of the parallel knock-out problem, Theoretical Computer Science 393 (2008) 182-195. DOI link to paper.
  12. Surahmat, E.T. Baskoro, and H.J. Broersma, The Ramsey numbers of large star and large star-like trees versus odd wheels, J. Combin. Math. Combin. Comput. 65 (2008) 153–162. link to mathscinet paper info.

Conference and Journal papers in 2007


  1. H.J. Broersma, G. Fijavz, T. Kaiser, R. Kuzel, Z. Ryjacek and P. Vrana, "Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks", Discrete Mathematics, in press (2007) DOI link to paper.
  2. H.J. Broersma, M. Johnson, D. Paulusma and I.A. Stewart, "The computational complexity of the parallel knock-out problem", Theoretical Computer Science, in press (2007) DOI link to paper.
  3. H.J. Broersma and X. Li, "On the complexity of dominating set problems related to the minimum all-ones problem", Theoretical Computer Science, Vol. 385 (1-3) (2007), pages 60-70. DOI link to paper.
  4. H.J. Broersma, M. Johnson and D. Paulusma, "Upper bounds and algorithms for parallel knock-out numbers", presented at SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity, Castiglioncello, Italy, June 5-8, 2007; Lecture Notes in Computer Science Vol. 4474, pages 324-336. DOI link to paper.
  5. H.J. Broersma, D. Paulusma and K. Yoshimoto, "On components of 2-factors in claw-free graphs", presented at EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, Seville, Spain, September 11-15, 2007; Electronic Notes in Discrete Mathematics, Vol. 29, pages 289-293. DOI link to paper.
  6. D. Bauer, H.J. Broersma, A. Morgana and E. Schmeichel, "Tutte sets in graphs I: Maximal Tutte sets and D-graphs", Journal of Graph Theory, Vol. 55 (4) (2007), pages 343-358. DOI link to paper.
  7. A.N.M. Salman and H.J. Broersma, "Path-kipas Ramsey numbers", Discrete Applied Mathematics, Vol. 155 (14) (2007), pages 1878-1884. DOI link to paper.
  8. M. Li, L. Xiong and H.J. Broersma, "Connected even factors in claw-free graphs", Discrete Mathematics, in press 2007. DOI link to paper.
  9. D. Bauer, H.J. Broersma, N. Kahl, A. Morgana, E. Schmeichel and T. Surowiec, "Tutte sets in graphs II: The complexity of finding maximum Tutte sets", Discrete Applied Mathematics, Vol. 155 (10) 2007, pages 1336-1343. DOI link to paper.
  10. H.J. Broersma, G. Fijavz, T. Kaiser, R. Kuzel, Z. Ryjacek and P. Vrana, "Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks", Electronic Notes in Discrete Mathematics, Vol. 28 2007, pages 55-59. DOI link to paper.
  11. A.N.M. Salman and H.J. Broersma, "On Ramsey numbers for paths versus wheels", Discrete Mathematics, Vol. 307 (7-8) 2007, pages 975-982. DOI link to paper.
  12. H.J. Broersma, L. Xiong and K. Yoshimoto, "Toughness and hamiltonicity in k-trees", Discrete Mathematics, Vol. 307 (7-8) 2007, pages 832-838. DOI link to paper.
  13. L. Wang, H.J. Broersma, C. Hoede, X. Li and G. Still, "Integral trees of diameter 6", Discrete Applied Mathematics, Vol. 155 (10) 2007, pages 1254-1266. DOI link to paper.
  14. H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman, "Improved upper bounds for lambda-backbone colorings along matchings and stars", Proceedings of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), LNCS 4362, pages 188-199. DOI link to paper.
  15. H.J. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, "Backbone colorings for graphs: tree and path backbones", Journal of Graph Theory,  Vol. 55 (2) (2007), pages 137-152. DOI link to paper.
  16. O.V. Borodin, H.J. Broersma, A.Glebov and J. van den Heuvel, "A new upper bound on the cyclic chromatic number", Journal of Graph Theory, Vol. 54 (1) 2007, pages 58-72. DOI link to paper.
  17. H.J. Broersma, F.V. Fomin, R. Kralovic and G.J. Woeginger, "Eliminating graphs by means of parallel knock-out schemes", Discrete Applied Mathematics, Vol. 155 (2) 2007, pages 92-102. DOI link to paper.

Conference and Journal papers in 2006


  1. H.J. Broersma (based on joint work with D. Bauer, N. Kahl, A. Morgana, E. Schmeichel and T. Surowiec), "Tutte sets: algorithmic and structural aspects", Oberwolfach Report, Vol. 7 2006, pages 441-446. [pdf-file]
  2. L. Wang, H.J. Broersma, C. Hoede, X. Li and G. Still, "Integral trees of diameter 6", Discrete Applied Mathematics, published online December 2006 DOI link to paper.
  3. A.N.M. Salman and H.J. Broersma, "On Ramsey numbers for paths versus wheels", Discrete Mathematics, published online December 2006. DOI link to paper.
  4. H.J. Broersma, L. Xiong and K. Yoshimoto, "Toughness and hamiltonicity in k-trees", Discrete Mathematics, published online September 2006. DOI link to paper.
  5. O.V. Borodin, H.J. Broersma, A.Glebov and J. van den Heuvel, "A new upper bound on the cyclic chromatic number", Journal of Graph Theory, published online 2 August 2006 DOI link to paper.
  6. H.J. Broersma, F.V. Fomin, R. Kralovic and G.J. Woeginger, "Eliminating graphs by means of parallel knock-out schemes", Discrete Applied Mathematics, published online June 2006 DOI link to paper.
  7. D. Bauer, H.J. Broersma and E. Schmeichel, "Toughness in Graphs – A Survey", Graphs and Combinatorics Vol. 22 (1), pages 1-35, April 2006.
  8. S. Brandt, H.J. Broersma, R. Diestel and M. Kriesell, "Global connectivity and expansion: long cycles and factors in f-connected graphs", Combinatorica Vol. 26 (1) 2006, pages 17-36.
  9. H.J. Broersma, A. Capponi and D. Paulusma, "On-line coloring of H-free bipartite graphs", Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC 2006), LNCS 3998, 284-295, 2006.
  10. H.J. Broersma, F.V. Fomin, J. Kratochvil and G.J. Woeginger, "Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult", Algorithmica Vol. 44 (4), pages 343-361, May 2006.
  11. H.J. Broersma, M. Johnson, D. Paulusma and I. A. Stewart, "The computational complexity of the parallel knock-out problem", Proceedings of the 7th Latin American Symposium (LATIN 2006), LNCS 3887, 250-261.
  12. A.N.M. Salman and H.J.Broersma, "Path-fan Ramsey numbers", Discrete Applied Mathematics Vol. 154 (9), pages 1429-1436, June 2006.
  13. L. Xiong and H.J.Broersma, "Subpancyclicity of line graphs and degree sums along paths", Discrete Applied Mathematics Vol. 154 (9), pages 1453-1463, June 2006.

Conference and Journal papers in 2005


  1. H.J. Broersma, F.V. Fomin, J. Kratochvil and G.J. Woeginger, "Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult". Algorithmica (online October 2005) link
  2. H.J. Broersma, "A general framework for coloring problems: old results, new results, and open problems". Combinatorial geometry and graph theory: Indonesia-Japan Joint Conference,IJCCGGT 2003, LNCS 3330, Springer- Verlag, 2005, pages 65--79.
  3. Surahmat, E.T. Baskoro, S. Uttunggadewa, and H.J. Broersma, "An upper bound for the Ramsey number of a cycle of length four versus wheels". Combinatorial geometry and graph theory: Indonesia-Japan Joint Conference,IJCCGGT 2003, 2005, LNCS 3330, Springer-Verlag, 2005, pages 181--184.
  4. A.N.M. Salman, H.J. Broersma, and C.A. Rodger, "More on spanning 2- connected subgraphs of alphabet graphs, special classes of grid graphs". Bull. Inst. Combin. Appl. 45 (2005), 17--32.
  5. L. Xiong, Z. Ryjácek, and H.J. Broersma, "On stability of the Hamiltonian index under contractions and closures". J. Graph Theory 49 (2005), 104--115.
  6. Surahmat, E.T. Baskoro, and H.J. Broersma, "The Ramsey number of fans versus K4". Bull. Inst. Combin. Appl. 43 (2005), 96--102.
  7. H.J. Broersma, X. Li, G.J. Woeginger, and S. Zhang, "Paths and cycles in colored graphs". Australas. J. Combin. 31 (2005), 299--311.
  8. G.J.M. Smit, Y. Guo, H.J. Broersma, M.A.J. Rosien, P.M. Heysters, and Th. Krol, "Mapping applications to a coarse grain reconfigurable system", Chapter 8 in: New Algorithms, Architectures and Applications for Reconfigurable Computing , ISBN: 1-4020-3127-0, Springer, 2005

Conference and Journal papers in 2004


  1. A.N.M. Salman and H.J. Broersma, "The Ramsey numbers of paths versus kipases". Workshop on Graphs and Combinatorial Optimization, Electron. Notes Discrete Math. 17, 2004, pages 251--255
  2. H.J. Broersma, D. Paulusma, G.J.M. Smit, F. Vlaardingerbroek, and G.J. Woeginger, "The computational complexity of the minimum weight processor assignment problem". Graph-theoretic concepts in computer science WG2004 , LNCS 3353, Springer-Verlag 2004, pages 189--200.
  3. H.J. Broersma, F.V. Fomin, and G.J. Woeginger, "Parallel knock-out schemes in networks". Mathematical foundations of computer science MFCS2004 , LNCS 3153, Springer-Verlag 2004, pages 204--214.
  4. H.L. Bodlaender, H.J. Broersma, F.V. Fomin, A.V. Pyatkin, and G.J. Woeginger, "Radio labeling with preassigned frequencies". SIAM J. Optim. 15 (2004), no. 1, pages 1--16.
  5. Surahmat, E.T. Baskoro, and H.J. Broersma, "The Ramsey numbers of large cycles versus small wheels". Integers 4 (2004), A10, 9 pages (electronic).
  6. L. Xiong, H.J. Broersma, X. Li, and M. Li, "The Hamiltonian index of a graph and its branch-bonds". Discrete Math. 285 (2004), no. 1-3, pages 279--288.
  7. A.N.M. Salman, H.J. Broersma, and C.A. Rodger, "A continuation of spanning 2-connected subgraphs in truncated rectangular grid graphs". J. Combin. Math. Combin. Comput. 49 (2004), pages 177--186.
  8. L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma, and P. Wolkotte. "Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture" , Proceedings of the International Conference on Field-Programmable Technology , 2004, pages 421--424.
  9. L.T. Smit, G.J.M. Smit, J.L. Hurink, H.J. Broersma, D. Paulusma and P. Wolkotte, "Run-time assignment of tasks to multiple heterogeneous processors", Proceedings of PROGRESS 2004 Embedded Systems Symposium , 2004, pages 185--192.

Conference and Journal papers in 2003


  1. A.N.M. Salman and H.J. Broersma, "The Ramsey numbers of paths versus fans". 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Electron. Notes Discrete Math. 13, 2003, 5 pages.
  2. H.J. Broersma, F.V. Fomin, P.A. Golovach, and G.J. Woeginger, "Backbone colorings for networks". Graph-theoretic concepts in computer science WG2003 , LNCS 2880, Springer-Verlag 2003, pages 131--142.
  3. A.N.M. Salman, H.J. Broersma, and E.T. Baskoro, "Spanning 2-connected subgraphs in alphabet graphs, special classes of grid graphs". J. Autom. Lang. Comb. 8 (2003), no. 4, pages 675--681.
  4. A.N.M. Salman, E.T. Baskoro, H.J. Broersma, and C.A. Rodger, "More on spanning 2-connected subgraphs in truncated rectangular grid graphs". Bull. Inst. Combin. Appl. 39 (2003), pages 31--38.
  5. Y. Guo, G.J.M. Smit, P.J.M. Heysters, and H.J Broersma , "A Graph Covering Algorithm for a Coarse Grain Reconfigurable System", Proceedings of LCTES 2003 , pages 199--208, ACM 2003, ISBN 1-58113-647-1.
  6. Y. Guo, G.J.M. Smit, H.J. Broersma, and P.J.M. Heysters, "Template Generation and Selection Algorithms", Proceedings of the 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications (IWSOC) , 2003, pages 2--5, IEEE Computer Society, ISBN 0-7695-1944-X.
  7. Y. Guo, G.J.M. Smit, H.J. Broersma, M.A.J. Rosien, and P.J.M. Heysters, "Mapping Applications to a Coarse Grain Reconfigurable System", Proceedings of 8th Asia-Pacific Computer Systems Architecture Conference (ACSAC2003) , 2003, pages 221--235, Springer-Verlag ISBN 3-540-20122-X.