Hajo Broersma

Orcid: 0000-0002-4678-3210

  • University of Twente, Department of Applied Mathematics, Enschede, The Netherlands
  • Durham University, Department of Computer Science, UK

According to our database1, Hajo Broersma authored at least 198 papers between 1987 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Properly colored and rainbow C 4 ${C}_{4}$ 's in edge-colored graphs.
J. Graph Theory, January, 2024

Sharp bounds for Laplacian spectral moments of digraphs with a fixed dichromatic number.
Discret. Math., January, 2024

The complexity of spanning tree problems involving graphical indices.
Discret. Appl. Math., 2024

Online Graph Coloring with Predictions.
Proceedings of the Combinatorial Optimization - 8th International Symposium, 2024

Sufficient conditions for properly colored C3's and C4's in edge-colored complete graphs.
Discret. Appl. Math., 2023

Polynomial algorithms for computing the isolated toughness of interval and split graphs.
Concurr. Comput. Pract. Exp., 2023

The effect of graph operations on the degree-based entropy.
Appl. Math. Comput., 2023

The Erdős-Gyárfás function with respect to Gallai-colorings.
J. Graph Theory, 2022

Toughness, forbidden subgraphs, and Hamiltonian-connected graphs.
Discuss. Math. Graph Theory, 2022

On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees.
Discret. Math., 2022

The Hamiltonian properties in <i>K</i><sub>1, <i>r</i></sub>-free split graphs.
Discret. Math., 2022

Integer Colorings with No Rainbow 3-Term Arithmetic Progression.
Electron. J. Comb., 2022

Some New Bounds for the Inverse Sum Indeg Energy of Graphs.
Axioms, 2022

Dopant network processing units: towards efficient neural network emulators with high-capacity nanoelectronic nodes.
Neuromorph. Comput. Eng., 2021

Edge-colored complete graphs without properly colored even cycles: A full characterization.
J. Graph Theory, 2021

Sufficient Spectral Radius Conditions for Hamilton-Connectivity of k-Connected Graphs.
Graphs Comb., 2021

Toughness, Forbidden Subgraphs and Pancyclicity.
Graphs Comb., 2021

On hamiltonicity of 1-tough triangle-free graphs.
Electron. J. Graph Theory Appl., 2021

Removable edges on a Hamilton cycle or outside a cycle in a 4-connected graph.
Discuss. Math. Graph Theory, 2021

Extremal problems and results related to Gallai-colorings.
Discret. Math., 2021

Almost eulerian compatible spanning circuits in edge-colored graphs.
Discret. Math., 2021

On sufficient spectral radius conditions for hamiltonicity.
Discret. Appl. Math., 2021

On the Spectra of General Random Mixed Graphs.
Electron. J. Comb., 2021

Extremality of VDB topological indices over f-benzenoids with given order.
Appl. Math. Comput., 2021

Classification with a disordered dopant-atom network in silicon.
Nat., 2020

Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs.
J. Graph Theory, 2020

Some algorithmic results for finding compatible spanning circuits in edge-colored graphs.
J. Comb. Optim., 2020

Conditions on subgraphs, degrees, and domination for hamiltonian properties of graphs.
Discret. Math., 2020

On sufficient degree conditions for traceability of claw-free graphs.
Discret. Math., 2020

Optimal Algorithm of Isolated Toughness for Interval Graphs.
Proceedings of the Parallel and Distributed Computing, Applications and Technologies, 2020

Properly Edge-colored Theta Graphs in Edge-colored Complete Graphs.
Graphs Comb., 2019

A polynomial algorithm for weighted scattering number in interval graphs.
Discret. Appl. Math., 2019

Decompositions of graphs based on a new graph product.
Discret. Appl. Math., 2019

Philosophy of Computation.
Proceedings of the Computational Matter, 2018

Computability and Complexity of Unconventional Computing Devices.
Proceedings of the Computational Matter, 2018

Conditions for graphs to be path partition optimal.
Discret. Math., 2018

Extremal benzenoid systems for two modified versions of the Randić index.
Appl. Math. Comput., 2018

Extremal and Degree Conditions for Path Extendability in Digraphs.
SIAM J. Discret. Math., 2017

An Exact Formula for all Star-Kipas Ramsey Numbers.
Graphs Comb., 2017

Cycle extension in edge-colored complete graphs.
Discret. Math., 2017

Computability and Complexity of Unconventional Computing Devices.
CoRR, 2017

On the complexity of edge-colored subgraph partitioning problems in network optimization.
Discret. Math. Theor. Comput. Sci., 2016

Forbidden subgraphs for hamiltonicity of 1-tough graphs.
Discuss. Math. Graph Theory, 2016

On fan-wheel and tree-wheel Ramsey numbers.
Discret. Math., 2016

On star-critical and upper size Ramsey numbers.
Discret. Appl. Math., 2016

Hamiltonian properties of almost locally connected claw-free graphs.
Ars Comb., 2016

A simulation tool for evolving functionalities in disordered nanoparticle networks.
Proceedings of the IEEE Congress on Evolutionary Computation, 2016

A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs.
Theor. Comput. Sci., 2015

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.
J. Graph Theory, 2015

Three Results on Cycle-Wheel Ramsey Numbers.
Graphs Comb., 2015

Characterizing Heavy Subgraph Pairs for Pancyclicity.
Graphs Comb., 2015

Best Monotone Degree Conditions for Graph Properties: A Survey.
Graphs Comb., 2015

On a directed tree problem motivated by a newly introduced graph product.
Electron. J. Graph Theory Appl., 2015

How tough is toughness?
Bull. EATCS, 2015

Ramsey numbers of trees versus fans.
Discret. Math., 2015

Closing the Gap on Path-Kipas Ramsey Numbers.
Electron. J. Comb., 2015

Computational Matter: Evolving Computational Solutions in Materials.
Proceedings of the Genetic and Evolutionary Computation Conference, 2015

On Toughness and Hamiltonicity of 2<i>K</i><sub>2</sub>-Free Graphs.
J. Graph Theory, 2014

Removable Edges and Chords of Longest Cycles in 3-Connected Graphs.
Graphs Comb., 2014

A remark on star-C4 and wheel-C4 Ramsey numbers.
Electron. J. Graph Theory Appl., 2014

Heavy subgraph pairs for traceability of block-chains.
Discuss. Math. Graph Theory, 2014

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width.
Theor. Comput. Sci., 2013

Toughness and Vertex Degrees.
J. Graph Theory, 2013

Tank-Ring Factors in Supereulerian Claw-Free Graphs.
Graphs Comb., 2013

Forbidden subgraph pairs for traceability of block-chains.
Electron. J. Graph Theory Appl., 2013

Fully decomposable split graphs.
Eur. J. Comb., 2013

Three complexity results on coloring Pk-free graphs.
Eur. J. Comb., 2013

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs.
Algorithmica, 2013

Improving the Performance of Periodic Real-time Processes: a Graph Theoretical Approach.
Proceedings of the 35th Communicating Process Architectures, 2013

Back to basics: Homogeneous representations of multi-rate synchronous dataflow graphs.
Proceedings of the 11th ACM/IEEE International Conference on Formal Methods and Models for Codesign, 2013

Determining the chromatic number of triangle-free 2P<sub>3</sub>-free graphs in polynomial time.
Theor. Comput. Sci., 2012

Updating the complexity status of coloring graphs without a fixed induced linear forest.
Theor. Comput. Sci., 2012

The complexity of finding uniform sparsest cuts in various graph classes.
J. Discrete Algorithms, 2012

Nascence Project: Nanoscale Engineering for Novel Computation Using Evolution.
Int. J. Unconv. Comput., 2012

How Many Conjectures Can You Stand? A Survey.
Graphs Comb., 2012

Degree Sequences and the Existence of k-Factors.
Graphs Comb., 2012

Pairs of forbidden induced subgraphs for homogeneously traceable graphs.
Discret. Math., 2012

Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs.
Proceedings of the 38th Euromicro Conference on Software Engineering and Advanced Applications, 2012

Hamiltonian connectedness in 4-connected hourglass-free claw-free graphs.
J. Graph Theory, 2011

Computing sharp 2-factors in claw-free graphs.
J. Discrete Algorithms, 2010

Narrowing Down the Gap on the Complexity of Coloring <i>P</i><sub><i>k</i></sub>-Free Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

The Complexity Status of Problems Related to Sparsest Cuts.
Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

On Coloring Graphs without Induced Forests.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Upper bounds and algorithms for parallel knock-out numbers.
Theor. Comput. Sci., 2009

On hamiltonicity of <i>P</i> <sub>3</sub>-dominated graphs.
Math. Methods Oper. Res., 2009

J. Discrete Algorithms, 2009

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs.
Graphs Comb., 2009

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.
Discuss. Math. Graph Theory, 2009

lambda-backbone colorings along pairwise disjoint stars and matchings.
Discret. Math., 2009

Complexity of conditional colorability of graphs.
Appl. Math. Lett., 2009

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Three Complexity Results on Coloring <i>P</i><sub><i>k</i></sub>-Free Graphs.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

The computational complexity of the parallel knock-out problem.
Theor. Comput. Sci., 2008

A New Algorithm for On-line Coloring Bipartite Graphs.
SIAM J. Discret. Math., 2008

J. Discrete Algorithms, 2008

Some families of integral graphs.
Discret. Math., 2008

Connected even factors in claw-free graphs.
Discret. Math., 2008

On the complexity of dominating set problems related to the minimum all-ones problem.
Theor. Comput. Sci., 2007

Backbone colorings for graphs: Tree and path backbones.
J. Graph Theory, 2007

A new upper bound on the cyclic chromatic number.
J. Graph Theory, 2007

Tutte sets in graphs I: Maximal tutte sets and D-graphs.
J. Graph Theory, 2007

On components of 2-factors in claw-free graphs.
Electron. Notes Discret. Math., 2007

Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks.
Electron. Notes Discret. Math., 2007

On Ramsey numbers for paths versus wheels.
Discret. Math., 2007

Toughness and hamiltonicity in k-trees.
Discret. Math., 2007

Integral trees of diameter 6.
Discret. Appl. Math., 2007

Path-kipas Ramsey numbers.
Discret. Appl. Math., 2007

Eliminating graphs by means of parallel knock-out schemes.
Discret. Appl. Math., 2007

Tutte sets in graphs II: The complexity of finding maximum Tutte sets.
Discret. Appl. Math., 2007

Improved Upper Bounds for <i>lambda</i> -Backbone Colorings Along Matchings and Stars.
Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

Toughness in Graphs - A Survey.
Graphs Comb., 2006

Subpancyclicity of line graphs and degree sums along paths.
Discret. Appl. Math., 2006

Path-fan Ramsey numbers.
Discret. Appl. Math., 2006

Global Connectivity And Expansion: Long Cycles and Factors In <i>f</i>-Connected Graphs.
Comb., 2006

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult.
Algorithmica, 2006

On-Line Coloring of H-Free Bipartite Graphs.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

On stability of the hamiltonian index under contractions and closures.
J. Graph Theory, 2005

Paths and cycles in colored graphs.
Australas. J Comb., 2005

Radio Labeling with Preassigned Frequencies.
SIAM J. Optim., 2004

The Ramsey Numbers of Paths Versus Kipases.
Electron. Notes Discret. Math., 2004

The hamiltonian index of a graph and its branch-bonds.
Discret. Math., 2004

Preface: The 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
Discret. Appl. Math., 2004

The Computational Complexity of the Minimum Weight Processor Assignment Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Parallel Knock-Out Schemes in Networks.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture.
Proceedings of the 2004 IEEE International Conference on Field-Programmable Technology, 2004

Spanning 2-Connected Subgraphs in Alphabet Graphs, Special Classes of Grid Graphs.
J. Autom. Lang. Comb., 2003

The Ramsey Numbers of Paths Versus Fans.
Electron. Notes Discret. Math., 2003

Preface: Volume 13.
Electron. Notes Discret. Math., 2003

Backbone Colorings for Networks.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

A graph covering algorithm for a coarse grain reconfigurable system.
Proceedings of the 2003 Conference on Languages, 2003

An Upper Bound for the Ramsey Number of a Cycle of Length Four Versus Wheels.
Proceedings of the Combinatorial Geometry and Graph Theory, 2003

A General Framework for Coloring Problems: Old Results, New Results, and Open Problems.
Proceedings of the Combinatorial Geometry and Graph Theory, 2003

Template Generation and Selection Algorithms.
Proceedings of the 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications (IWSOC'03), 30 June, 2003

Mapping Applications to a Coarse Grain Reconfigurable System.
Proceedings of the Advances in Computer Systems Architecture, 2003

Forbidden subgraphs that imply hamiltonian-connectedness.
J. Graph Theory, 2002

A Fan Type Condition For Heavy Cycles in Weighted Graphs.
Graphs Comb., 2002

More Progress on Tough Graphs - The Y2K Report.
Electron. Notes Discret. Math., 2002

Isomorphisms and traversability of directed path graphs.
Discuss. Math. Graph Theory, 2002

Heavy cycles in weighted graphs.
Discuss. Math. Graph Theory, 2002

Degree sums and subpancyclicity in line graphs.
Discret. Math., 2002

On some intriguing problems in hamiltonian graph theory--a survey.
Discret. Math., 2002

A note on minimum degree conditions for supereulerian graphs.
Discret. Appl. Math., 2002

Some approaches to a conjecture on short cycles in digraphs.
Discret. Appl. Math., 2002

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion.
Discret. Appl. Math., 2002

More About Subcolorings.
Computing, 2002

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems.
Algorithmica, 2002

Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.
Proceedings of the Algorithm Theory, 2002

Radio Labeling with Pre-assigned Frequencies.
Proceedings of the Algorithms, 2002

On factors of 4-connected claw-free graphs.
J. Graph Theory, 2001

Paths and Cycles in Colored Graphs.
Electron. Notes Discret. Math., 2001

Preface: Volume 8.
Electron. Notes Discret. Math., 2001

A <i>σ<sub>3</sub></i> type condition for heavy cycles in weighted graphs.
Discuss. Math. Graph Theory, 2001

Strengthening the closure concept in claw-free graphs.
Discret. Math., 2001

Degree-preserving trees.
Networks, 2000

Closure Concepts: A Survey.
Graphs Comb., 2000

Heavy paths and cycles in weighted graphs.
Discret. Math., 2000

A Linear Time Algorithm for Minimum Fill-in and Treewidth for Distance Hereditary Graphs.
Discret. Appl. Math., 2000

Not Every 2-tough Graph Is Hamiltonian.
Discret. Appl. Math., 2000

Independent Sets in Asteroidal Triple-Free Graphs.
SIAM J. Discret. Math., 1999

Various results on the toughness of graphs.
Networks, 1999

Another equivalent of the graceful tree conjecture.
Ars Comb., 1999

Independence trees and Hamilton cycles.
J. Graph Theory, 1998

Closure concepts for claw-free graphs.
Discret. Math., 1998

A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

Degree-Preserving Forests.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Spanning trees with many or few colors in edge-colored graphs.
Discuss. Math. Graph Theory, 1997

Dirac's minimum degree condition restricted to claws.
Discret. Math., 1997

Cycles through subsets with large degree sums.
Discret. Math., 1997

A note on the minimum size of a vertex pancyclic graph.
Discret. Math., 1997

Spanning trees with pairwise nonadjacent endvertices.
Discret. Math., 1997

Algorithms for the Treewidth and Minimum Fill-in of HHD-Free Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Toughness and hamiltonicity in almost claw-free graphs.
J. Graph Theory, 1996

Hamiltonicity of regular 2-connected graphs.
J. Graph Theory, 1996

Toughness and longest cycles in 2-connected planar graphs.
J. Graph Theory, 1996

On graphs satisfying a local ore-type condition.
J. Graph Theory, 1996

The connectivity of the leaf-exchange spanning tree graph of a graph.
Ars Comb., 1996

Bipartite regular graphs with fixed diameter.
Networks, 1995

Cycles through particular subgraphs of claw-free graphs.
J. Graph Theory, 1995

Long cycles in graphs with prescribed toughness and minimum degree.
Discret. Math., 1995

On generalizing a theorem of Jung.
Ars Comb., 1995

A closure concept based on neighborhood unions of independent triples.
Discret. Math., 1994

Subgraphs, Closures and Hamiltonicity.
Discret. Appl. Math., 1994

Decomposition of bipartite graphs under degree constraints.
Networks, 1993

Cycles containing all vertices of maximum degree.
J. Graph Theory, 1993

Generating all 3-connected 4-regular planar graphs from the octahedron graph.
J. Graph Theory, 1993

Long paths and cycles in tough graphs.
Graphs Comb., 1993

A generalization of Ore's Theorem involving neighborhood unions.
Discret. Math., 1993

Long cycles, degree sums and neighborhood unions.
Discret. Math., 1993

Coloring a graph optimally with two colors.
Discret. Math., 1993

A note on K<sub>4</sub>-closures in hamiltonian graph theory.
Discret. Math., 1993

On "The Matching Polynomial of a Polygraph".
Discret. Appl. Math., 1993

An Affirmative Action Graph (D. J. Newman).
SIAM Rev., 1992

The connectivity of the basis graph of a branching greedoid.
J. Graph Theory, 1992

Long dominating cycles and paths in graphs with large neighborhood unions.
J. Graph Theory, 1991

Path graphs.
J. Graph Theory, 1989

A generalization of a result of Häggkvist and Nicoghossian.
J. Comb. Theory B, 1989

Existence of Δ<sub>λ</sub>-cycles and Δ<sub>λ</sub>-paths.
J. Graph Theory, 1988

3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian.
J. Graph Theory, 1987