24 problems

Let $p$ be a prime number, and let $\mathcal C_{\geq p}^{\mathrm{prime}}$ be the family of all cycles of length at least $p$. For integers $n$ and $r$ satisfying $r<p$, let…

Let $k\geq 2$ and let $n$ be sufficiently large. Let $G$ be an $n$-vertex graph containing no cycle $C_{3\ell+1}$ for any integer $\ell\geq k$. For $r\geq 2$, write $N_r(G)$ for th…

Let $f(n,k)$ denote the maximal-clique deficiency parameter and let $c(n,k)$ denote the layered-tree parameter for $k$-uniform hypergraphs, as defined in the paper. Exponential rel…

Linear threshold conjecture. If

Jung–Keszegh–Pálvölgyi–Yuditsky conjecture. For all $k\geq2$ there exists a constant $c_k<1$ such that, whenever

Feige–Pauzner conjecture. For all $n>0$,

Let $G$ be a finite graph, and call it $r$-locally chordal if every ball of radius $r$ in $G$ is chordal. Let $|V(G)|$ denote the number of vertices of $G$ and let…

Asymptotic clique-ratio conjecture. There exist positive constants $\varepsilon_1$ and $\varepsilon_2$ such that

Localized hypergraph clique-weight conjecture. One has

Frohmader's localized clique-weight conjecture. For every $m$-edge graph $G$,

Let $G$ be a 2-connected $n$-vertex graph with $n\ge 3$, and let $uv$ be an edge of $G$. Let $k\ge 4$ and $s\ge 2$ be integers, and write … where $0\le t\le k-4$. Here $N_s(G)$ den…

Let $r$ and $k$ be integers satisfying $1\le r\le k$ and $k\ge 3$. The Ramsey–Turán tiling function ${\bf{RTT}}_r(K_k)$ is defined as the asymptotic minimum-degree threshold for fo…

Let $G$ be a $2$-connected graph on $n$ vertices, and let $ab$ be an edge of $G$. Let $r\geq 4$ and $s\geq 2$ be integers, and write … for some $0\leq t\leq r-4$. Here $N_s(G)$ den…

Threshold equality conjecture. For all $r>k\ge 2$,

Let $t_{k-1}(n)$ denote the maximum number of edges in a $K_{k-1}$-free graph on $n$ vertices, and let $\tau_k(G)$ be the minimum size of a vertex set meeting every copy of $K_k$ i…

Let $V_1,V_2,\ldots,V_{k-1}$ be the vertex classes of the balanced Turán graph $T_{k-1}(n)$, with sizes satisfying…

Gustavsson–Nash-Williams conjecture. For every $r\ge 3$, there exists an $n_0=n_0(r)$ such that every $K_r$-divisible graph $G$ on $n\ge n_0$ vertices with

Let $\textup{cliques}(n,t,k)$ denote the maximum number of $k$-cliques in an $n$-vertex graph with no $K_t$-minor. Very-large-clique conjecture. There is some…

Let $\textup{cliques}(n,t,k)$ denote the maximum number of $k$-cliques in an $n$-vertex graph with no $K_t$-minor. Large-clique conjecture. There are constants $c_1,c_2>0$ such tha…

Let $\textup{cliques}(n,t)$ denote the maximum number of cliques in an $n$-vertex graph with no $K_t$-minor. Clique-count conjecture. … The bound is motivated by complete multipart…

Let $G$ be a graph. Write $\Delta$ for its maximum degree, $\omega$ for its clique number, and $\chi$ for its chromatic number. Let $\mathcal{H}(G)$ be the subgraph induced by the…

Upper-tail exponent conjecture. For any $H$ and $p>n^{-1/m_H}$,

Let $Q(n,r)$ denote the minimum clique number among graphs on $n$ vertices with chromatic number $r$. The clique-number conjecture. Let $k$ be a positive integer. If $n$ is suffici…

Let $n$ and $\beta$ be such that the family of graphs $\mathcal{G}(n,\beta)$ is defined, and let $(n,\beta)$ be feasible when $G[V_0]$ is triangle-free for…