Let $f(d)$ be the smallest integer such that every connected bridgeless graph of diameter $d$ admits an orientation with directed diameter at most $f(d)$. Chv\'atal and Thomassen (1978) proved $\left\lceil{d^2}/{2}\right\rceil+d\le f(d) \le 2d^2+2d$. In this paper, we prove that $f(d)\le \left\lceil d^2/2\right\rceil+6...
Jiang-Dong Ai, Yao-Jun Chen, Yao-Kun Feng et al.· 0 citations
The Ramsey number $r(H)$ of a graph $H$ is the minimum positive integer $N$ such that every red/blue edge-coloring of the complete graph $K_N$ on $N$ vertices contains a monochromatic copy of $H$. The Ramsey multiplicity $M(H,n)$ is the minimum number of monochromatic copies of $H$ over all red/blue edge-colorings of $...
Ting Huang, Jun-Ying Lu, Jia-Bao Yang et al.· 0 citations
For a fixed digraph $F$, let $\operatorname{ex}_2^+(n,F)$ be the maximum of $\sum_{v\in V(D)}d_D^+(v)^2$ over all $n$-vertex $F$-free digraphs. Ai et al. [arXiv:2606.03520, 2026] asked for which self-converse tournament $F$ one can determine $\operatorname{ex}_2^+(n,F)$. Let $TT_r$ denote a transitive tournament on $r$...
Let $\rho(n,d)$ denote the maximum adjacency spectral radius among all connected nonregular graphs of order $n$ and maximum degree $d$. A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for $d=3,4$ and formulated two conjectures for general $...
Erd\H{o}s et al. (JCT-B, 1989) conjectured that, for integers $r\ge 2$ and $\delta\ge 2$ with $3r-1\mid\delta$, every connected $K_{2r+1}$-free graph of order $n$ and minimum degree $\delta$ has diameter at most $ \frac{3r-1}{r}\cdot \frac{n}{\delta}+O(1)$. Czabarka et al. (JCT-B, 2021) later proposed the following gen...
Let $f(k)$ denote the smallest integer such that every oriented graph $D$ with chromatic number at least $f(k)$ contains every oriented tree on $k$ vertices. Burr (1980) showed that $f(k)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}alves and Reinald (2025) proved that $f(k)=O(k^{3/2})$. In this paper,...
The \emph{$k$-color Ramsey number} $R_k(C_{2\ell+1})$ is the least integer $n$ such that any $k$-edge-coloring of a complete graph $K_n$ has a monochromatic odd cycle $C_{2\ell+1}$. Axenovich, Cames van Batenburg, Janzer, Michel, and Rundstr\"om~(JCT-B, 2026) recently proved \[ R_k(C_{2\ell+1})\le (4\ell-2)^k k^{k/\ell...