20 problems

Let $s$ be a positive integer, and let $c_s$ be a constant such that $G$ is a graph with $N$ vertices containing no odd cycles of length less than $c_sN^{1/s}$. Erdős's conjecture.…

Let $k\geq 3$ be an integer, and let $\chi_S(n,e,L)$ denote the minimum number of colors in an edge-coloring of an $n$-vertex graph with at least $e$ edges in which every copy of…

Let $k\ge2$, and let $G$ be an $n$-vertex graph with $\lfloor n^2/4\rfloor+1$ edges. An edge occurs in $C_{2k+1}$ if it belongs to an odd cycle of length $2k+1$. Erdős–Faudree–Rous…

Odd-cycle blowup conjecture. There is a $C_{2k+1}$-blowup $G^*$ such that

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…

Let $k$ be a positive integer, and let $C_{2k+1}$ denote the odd cycle of length $2k+1$. A blowup of $C_{2k+1}$ is obtained by replacing its vertices with independent sets and its…

Let $k$ and $\ell$ be positive integers with $\ell>k$. Forbidding $C_{2k-1}$, or more generally a graph $F$ with $\gamma(F)=k$, consider the problem of maximizing the number of cop…

Let $\mathsf{C}_k$ be an odd cycle, and let $L(k,d)$ denote the lower bound for its independence number obtained in Bohman's result. Bohman's conjecture. The lower bound is the exa…

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 $t\geqslant 1$, let $\delta>0$, and let $G$ be a graph. Write $\mathscr{C}_{2t+1}=\{C_3,C_5,\dots,C_{2t+1}\}$ for the family of odd cycles of length at most $2t+1$, and let…

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…

Let $n$, $k$, and $q$ be positive integers, and let $\mathop{}\!\mathrm{ex}(n,C_{2k+1},q)$ denote the relevant extremal number for $q$-ary vectors, while…

Homomorphism-threshold conjecture. Then

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

For integers $k\ge 2$, $t\ge 1$, and $q=2t+1$, let $C_{k,q}$ be the graph formed by $k$ odd cycles of length $q$ intersecting in a common vertex. Let $S_{n,kt}$ be the graph consis…

Let $\Gamma$ be an $(n,d,\lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose nontrivial adjacency eigenvalues have absolute value at most $\lambda$. Let $k$ be a pos…

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…

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…