14 problems

Burr–Erdős–Graham–Sós conjecture. For every integer $k\ge 3$,

Let $r(G)$ be the maximum chromatic number of a subgraph spanned by an odd cycle of a graph $G$, and let $\chi(G)$ be the chromatic number of $G$. Linear separation conjecture. For…

Let $G$ be a graph, and let $r(G)$ denote the maximum chromatic number of a subgraph spanned by an odd cycle of $G$, while $\chi(G)$ denotes the chromatic number of $G$. Gyárfás' b…

Maximum likelihood conjecture. For every $m\geq 3$ and every edge probability mass $\mu$,

Let $T$ be the set of positive integers under consideration, and let $G(\mathbb{Q}^3,\sqrt{t})$ denote the graph whose vertices are points of $\mathbb{Q}^3$ with adjacency determin…

Let $T$ be the set of positive integers under consideration in the paper, let $T_1=\{22,58,70,82,142,190,298,330,358,382,478,658,742,862,1222,1978\}$, and let $C_3(t)$ denote the n…

Homomorphism-threshold conjecture. Then

Spectral odd-cycle containment conjecture. Under this condition, $G$ contains at least one cycle from

For integers $k$ and $\ell$, write $\operatorname{ex}(n,C_k,C_\ell)$ for the maximum number of copies of the cycle $C_k$ in an $n$-vertex graph containing no copy of $C_\ell$. Let…

Subquadratic odd-cycle conjecture. There exists an $\epsilon>0$ such that

Let $k\geq 2$ and let $n>3$ be odd. Write $R_k(C_n)$ for the least integer $N$ such that every colouring of the edges of the complete graph $K_N$ with $k$ colours contains a monoch…

Let $G$ be an $n$-vertex graph with … Let $C_{2k+1}$ denote the cycle of length $2k+1$, and say that an edge occurs in $C_{2k+1}$ if it belongs to a copy of that cycle. Fix an inte…

Let $c>1$ be fixed, let $G\sim G(n,c/n)$, and let $C_{2\ell+1}$ be the cycle of length $2\ell+1$. A graph homomorphism from $G$ to $C_{2\ell+1}$ is a vertex map preserving adjacenc…

Let $G$ be an $n$-vertex graph with $e$ edges, and let a $C_{2k+1}$-edge mean an edge contained in a cycle of length $2k+1$. Assume that $e>n^2/4$, $k\geq 3$, and $n>n_k$, where…