23 problems

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 ……

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 $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 $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…

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 $\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…

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 $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 graph on $n$ vertices with maximum degree $d$. Write … Here $q$ and $r$ are the quotient and remainder in the division of $n$ by $d+1$. Gan–Loh–Sudakov's conjecture. T…

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…

Let $\mathcal D(k)$ be the class of graphs whose vertex degrees are at most $k$. Bounded-degree conjecture. … The source gives a general upper bound from graph colouring and says t…

Let $f_G(n,m)$ denote the least number of independent $n$-sets in a graph $G$ that guarantees a rainbow independent set of size $m$. Maximum-degree-two conjecture. If $G$ has maxim…

Let $\mathcal{G}(\Delta,\omega)$ be the class of graphs with maximum degree at most $\Delta$ and clique number at most $\omega$, and let $f_t(\Delta,\omega)$ be the supremum of…

For $k\geq 2$, let $\widetilde{\operatorname{BT}}(k)$ be obtained from $T_2(2k)$ by deleting an edge and adjoining a new vertex to the two endpoints of that edge, and let … Let…

Let $G$ be a graph with no isolated vertices, let $\Delta$ be its maximum degree, let $n(G)$ denote its number of vertices, and let $\nu_{ac}(G)$ denote its acyclic matching number…

Bounded-degree spanning graph threshold conjecture. The random graph $G(n,p)$ almost surely contains $H$ whenever

Let $\bar d(G)$ denote the upper density of the vertex set of a graph $G$ embedded in $K_\NN$. Bounded-degree density conjecture. For every $\Delta\in\NN$, there exists $c>0$ such…

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…

Let $G$ be a connected graph with maximum degree $Deltageq 3$. Let $C5^2$ be the graph obtained from a $5$-cycle by replacing its vertices with independent sets of order $2$, and…

Let $G$ be a graph, let $m(G)$ denote its number of edges, and let $C_5^2$ denote the graph obtained by replacing each vertex of a $5$-cycle with an independent set of order $2$. A…

A graphing is a measure-preserving graph limit object for bounded-degree graphs, and a unimodular distribution is a distribution on rooted countable graphs satisfying the unimodula…

Square-root query-complexity conjecture. For every $H$, being $H$-minor free can be tested with one-sided error using $\tilde{O}(\sqrt{n})$ queries, where $n$ is the number of vert…