Henning and Yeo conjectured an upper bound on the identifying vertex cover number of a graph in terms of its order, size, and maximum degree. A two-parameter family $H_{t,r}$ of connected diameter-two graphs disproves the bound for every maximum degree at least four; after denominators are cleared, its margin is exactly $-(t-1)(r-1)$. The complement relation $\tau_D=n-\rho$ exposes the mechanism: diameter-two fibres admit at most one packing vertex, while degree deficit accumulates under tree gluing with controlled port loads. Writing $A_\Delta$ for the supremal additive gap at maximum degree exactly $\Delta$, an exact transfer formula gives $A_\Delta=+\infty$ for every $\Delta\ge 4$, using Petersen fibres in degrees four and five and the original $H_{t,r}$ blocks in higher degrees. If $c_\Delta$ denotes the corresponding supremal gap per vertex, rooted rook-graph fibres match a universal square-graph packing bound to first order. Consequently, $c_\Delta\sim 1/\Delta$, equivalently $\Delta c_\Delta\to 1$ as $\Delta\to\infty$.
In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematica...
Wouter Cames van Batenburg, J. Goedgebeur, Jorik Jooken· 0 citations
Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood (2023) conjectured that graphs of degree-$d$ polynomial growth can be embedded into the strong product of $d$ trees, each with linear growth, and a constant-size complete graph. Very recently, the case $d = 4$ of the conjecture was disproved by Illingworth,...
Fang and Lin [J. Algebraic Combin. 63 (2026), Art.~58] asked whether, whenever $F$ is edge-color-critical with $\chi(F)=r+1$, every non-$r$-partite, $F$-free graph of maximum adjacency spectral radius must also maximize the number of edges. We give a negative answer. Let $F=K_1\vee\mu(K_3)$, where $\mu(K_3)$ is the Myc...
In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E(G) \to E(P)$ mapping any two adjacent edges of $G$ to two adjacent edges of the Petersen graph $P$. A positive resolution of Jaeger's conjecture would have immediately resolved several other famous and long-s...
J. Goedgebeur, Jorik Jooken, Edita Máčajová et al.· 0 citations
For positive integers $n,r,t$, let $\delta(n,r,t)$ denote the maximum possible minimum degree of a balanced $r$-partite graph with parts of size $n$ and chromatic number at most $t$. Lo, Treglown and Zhao established a general upper bound for this parameter and used it, together with explicit constructions, to determin...
Tuza conjectured that every finite simple graph $G$ satisfies $\tau(G) \leq 2\nu(G)$, where $\nu(G)$ is the maximum number of pairwise edge-disjoint triangles and $\tau(G)$ is the minimum number of edges whose deletion makes $G$ triangle-free. Puleo proved the conjecture for every graph of maximum average degree less t...
A. Gupta· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
