41 problems

Let $G$ be a graph on $n$ vertices with maximum degree at most $r$, and let $t\geq 3$ be fixed. Let $a$ be as large as possible subject to $n=a(r+1)+b$, with $0\leq b<r+1$. Gan–Loh…

Rödl–Szemerédi conjecture. For every $d\geq 3$ there exist $\varepsilon>0$ and a sequence of graphs $(G_n)$ on $n$ vertices and maximum degree at most $d$ such that

Let $M(\Delta \leqslant k)$ denote the maximum inversion diameter among graphs whose maximum degree is at most $k$. The complete graph gives $M(\Delta \leqslant k) \geqslant k$. Ma…

Fix a maximum degree $d$. Let $(G_n)_{n\geq1}$ be a sequence of finite connected graphs, with $G_n=(V_n,E_n)$, $|V_n|\to\infty$, and maximum degree at most $d$. The polylogarithmic…

Trotter's conjecture. For every fixed $Delta$ and $r$, the induced Ramsey number $r_{\operatorname{ind}}(H;r)$ is polynomial in $n$ for every $n$-vertex graph $H$ of maximum degree…

Mohar's conjecture. For every integer $d\geq 3$, if $G$ has maximum degree at most $d$, then both median eigenvalues have absolute value at most $\sqrt{d-1}$. The paper proves the…

Let $G$ be a simple graph of order $n$, with adjacency eigenvalues $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$. Its median eigenvalues are $\lambda_h$ and $\lambda_\ell$, wh…

Grinshpun–Sárközy conjecture. For every positive integer $r$ there exists a constant $C_r$ such that, for every $\Delta\geq 2$ and every $\Delta$-bounded graph sequence…

Let $t\geq 3$, let $G$ be a graph with $m$ edges and maximum degree at most $r$, and write … Here $k_t(G)$ denotes the number of copies of $K_t$ in $G$, $K_{r+1}$ is the complete g…

Let $G$ be a simple graph of order $n$, with adjacency eigenvalues $\lambda_1 \geq \cdots \geq \lambda_n$, and let $\lambda_h$ and $\lambda_\ell$ be its median eigenvalues, where ……

Let $k\geq 3$, and let a $k$-degree graph mean a graph of maximum degree at most $k$. A coloring is $(1^{k-1},2^{k-1},3)$-packing colorable if its vertices can be partitioned into…

Let $cDelta\textgreater{}0$ be fixed, and let $C_cDelta$ be the constant in a linear Ramsey bound for graphs of maximum degree $cDelta$. The known upper bound has the form…

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, and let $X,Y\subseteq V(G)$. A set of vertices separates $X$ and $Y$ if it intersects every $X$-$Y$-path; paths are p…

Folklore universality conjecture. For every $\Delta\geq 3$, this lower bound gives the correct order of magnitude for the threshold probability of $G(n,p)$ to be…

Maximum Mostar index conjecture. The maximum Mostar index among graphs of order $n$ and maximum degree at most $\Delta$ is

Aashtab et al.'s conjecture. Every graph $G$ of even order satisfies

Let $G$ be a graph. A hole is an induced cycle of length at least four, and an even hole is a hole with an even number of vertices. The maximum degree of $G$ is denoted by…

Let $\overleftrightarrow{r_3}(H)$ be the three-color directed Ramsey number, and let an acyclic digraph have maximum degree at most $\Delta$. Three-color directed-Ramsey conjecture…

For $k,\Delta\geq 1$ and $n>\Delta$, let $H_{k,n,\Delta}$ be an acyclic digraph with $n$ vertices and maximum degree $\Delta$ maximizing $\ovar{r_k}(H)$. Super-polynomial growth co…

Deterministic FPTAS conjecture. There is an FPTAS for

Let $\Delta\in\mathbb{N}$. A graph has bounded maximum degree at most $\Delta$ when $\Delta(G)\leq\Delta$. Burr–Erdős conjecture. There exists $c=c(\Delta)>0$ such that every $2$-e…

Let $A$ be a symmetric nonnegative matrix, and let $\operatorname{EVAL}^{(\Delta)}(A)$ denote the problem of evaluating the corresponding graph homomorphism partition function on g…

Fix positive integers $d$ and $r$, and let $G$ be a graph on $d+1+r$ vertices with maximum degree $d$. For a fixed integer $t\ge 3$, let a clique of size $t$ mean a complete subgra…

Fix positive integers $d$ and $n$ with $d+1 \le n \le 2d+1$. Let $G$ be an $n$-vertex graph with maximum degree $d$, and write $r=n-d-1$. Galvin's conjecture. The maximum number of…

Let $f_{\mathcal D(k)}(n)$ denote the full-rainbow parameter for the class $\mathcal D(k)$ of graphs with maximum degree at most $k$, and let $q$ be the quantity used in the source…