H. Broersma

activity

20072025

most citedOn a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees

5 citations · 15 across the 15 of their papers we have counts for

collaborators

17 papers

math.CO2025

Path Extendable Tournaments

Zan-Bo Zhang, Weihua He, Hajo Broersma +1

A digraph $D$ is called \emph{path extendable} if for every nonhamiltonian (directed) path $P$ in $D$ , there exists another path $P^{'}$ with the same initial and terminal verti…

math.CO2024

Closures and heavy pairs for hamiltonicity

Wangyi Shang, Hajo Broersma, Shenggui Zhang +1

We say that a graph $G$ on $n$ vertices is ${H, F}$ - $o$ -heavy if every induced subgraph of $G$ isomorphic to $H$ or $F$ contains two nonadjacent vertices with degree sum at least…

math.CO2024

Connected Turán numbers for Berge paths in hypergraphs

Lin-Peng Zhang, Hajo Broersma, Ervin Győri +2

Let $F$ be a family of $r$ -uniform hypergraphs. Denote by $\ex^{\mathrm{conn}}_r(n,\mathcal{F})$ the maximum number of hyperedges in an $n$ -vertex connected $r$ -uniform h…

math.CO2024

A note on generalized crowns in linear r-graphs

Lin-Peng Zhang, Hajo Broersma, Ligong Wang

An $r$ -graph $H$ is a hypergraph consisting of a nonempty set of vertices $V$ and a collection of $r$ -element subsets of $V$ we refer to as the edges of $H$ . An $r$ -graph $H$ is ca…

cs.DS2023

Online Graph Coloring with Predictions

Antonios Antoniadis, Hajo Broersma, Yang Meng

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are…

math.CO2023

Turán numbers of general hypergraph star forests

Lin-Peng Zhang, Hajo Broersma, Ligong Wang

Let $F$ be a family of $r$ -uniform hypergraphs, and let $H$ be an $r$ -uniform hypergraph. Then $H$ is called $F$ -free if it does not contain any member of $\mat…

math.CO2023

Sharp bounds for Laplacian spectral moments of digraphs with a fixed dichromatic number

Xiuwen Yang, Hajo Broersma, Ligong Wang

The $k$ -th Laplacian spectral moment of a digraph $G$ is defined as $\sum_{i = 1}^{n} λ_{i}^{k}$ , where $λ_{i}$ are the eigenvalues of the Laplacian matrix of $G$ and $k$ is a nonnegative in…

math.CO2021★ 5 cited

On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees

Xiangxiang Liu, Hajo Broersma, Ligong Wang

We partly confirm a Brualdi-Solheid-Turán type conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdős-Sós Conjecture that any tree of order $t$ is…

math.CO2021

Growth rates of the bipartite Erdős-Gyárfás function

Xihe Li, Hajo Broersma, Ligong Wang

Given two graphs $G, H$ and a positive integer $q$ , an $(H, q)$ -coloring of $G$ is an edge-coloring of $G$ such that every copy of $H$ in $G$ receives at least $q$ distinct colors.…

math.CO2021★ 4 cited

Spectral radius conditions for the existence of all subtrees of diameter at most four

Xiangxiang Liu, Hajo Broersma, Ligong Wang

Let $μ (G)$ denote the spectral radius of a graph $G$ . We partly confirm a conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdős-Sós Conjecture th…

math.CO2020★ 1 cited

The Erdős-Gyárfás function with respect to Gallai-colorings

Xihe Li, Hajo Broersma, Ligong Wang

For fixed $p$ and $q$ , an edge-coloring of the complete graph $K_{n}$ is said to be a $(p, q)$ -coloring if every $K_{p}$ receives at least $q$ distinct colors. The function $f(n, p, q)…

cs.LG2020

Dopant Network Processing Units: Towards Efficient Neural-network Emulators with High-capacity Nanoelectronic Nodes

Hans-Christian Ruiz-Euler, Unai Alegre-Ibarra, Bram van de Ven +3

The rapidly growing computational demands of deep neural networks require novel hardware designs. Recently, tunable nanoelectronic devices were developed based on hopping electrons…

math.CO2020

Extremal problems and results related to Gallai-colorings

Xihe Li, Hajo Broersma, Ligong Wang

A Gallai-coloring (Gallai- $k$ -coloring) is an edge-coloring (with colors from ${1, 2, \dots, k}$ ) of a complete graph without rainbow triangles. Given a graph $H$ and a positive…

math.CO2017★ 3 cited

Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs

Ruonan Li, Hajo Broersma, Shenggui Zhang

It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Δ^{m o n} (G) \leq n - 3 k + 1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confir…

cs.ET2017★ 2 cited

Computability and Complexity of Unconventional Computing Devices

Hajo Broersma, Susan Stepney, Goran Wendin

We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete proble…

cs.DS2013

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Hajo Broersma, Jiří Fiala, Petr A. Golovach +3

Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval gr…

cs.DM2007

Complexity of the conditional colorability of graphs

Xueliang Li, Xiangmei Yao, Wenli Zhou

For an integer $r > 0$ , 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 t…