Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
5 solved out of 14 shown
If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots $ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$.
Conjectured by Hajnal and Erdős and solved by Liu and Montgomery [LiMo20]. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.
If $G$ is a graph which contains odd cycles of $\leq k$ different lengths then $\chi(G)\leq 2k+2$, with equality if and only if $G$ contains $K_{2k+2}$.
Conjectured by Bollobás and Erdős. Bollobás and Shelah have confirmed this for $k=1$. Proved by Gyárfás [Gy92], who proved the stronger result that, if $G$ is 2-connected, then $G$ is either $K_{2k+2}$ or contains a vertex of degree at most $2k$.

A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.

Additional thanks to: David Penman
Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?
Conjectured by Erdős and Simonovits, who could not even prove that at least $2$ copies of $C_4$ are guaranteed.

He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.

Does every infinite graph with infinite chromatic number contain a cycle of length $2^n$ for infinitely many $n$?
Conjectured by Mihók and Erdős. It is likely that $2^n$ can be replaced by any sufficiently quickly growing sequence (e.g. the squares).
$1000
Does every graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?
Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove much stronger result: if the average degree of $G$ is sufficiently large, then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

Additional thanks to: Yuval Wigderson
Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is the sum $\sum\frac{1}{a_i}$ minimised when $G$ is a complete bipartite graph?
Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.
Is it true that for every pair $a,b\geq 1$ such that either $a$ is even or both $a$ and $b$ are odd then there is $c=c(a,b)$ such that every graph with average degree at least $c$ contains a cycle whose length is $\equiv a\pmod{b}$?
This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(a,b)$ is unknown.
$100
Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?
Bollobás proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers. Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although conjectures that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

Additional thanks to: Richard Montgomery
$500
Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?
Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82]. Rödl [Ro82] has proved this for hypergraphs. It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$.
The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\ell \in A$. Let $f(n)$ count the number of possible such $A$. Prove that $f(n)=o(2^n)$.
Conjectured by Erdős and Faudree, who showed that $f(n) > 2^{n/2}$, and further speculate that $f(n)/2^{n/2}\to \infty$. This conjecture was proved by Verstraëte [Ve04], who proved the number of such sets is \[\ll 2^{n-n^c}\] for some constant $c>0$.
Additional thanks to: Tuan Tran
For every $k\geq 3$ and $n\geq 2$ is there some finite $f(n,k)$ such that every graph of chromatic number $\geq f(n,k)$ contains a subgraph of girth at least $k$ and chromatic number at least $n$?
Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $k=3$ case. The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.
Is there some $F(n)$ such that every graph with chromatic number $\aleph_1$ has, for all large $n$, a subgraph with chromatic number $n$ on at most $F(n)$ vertices?
Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82]. This fails if the graph has chromatic number $\aleph_0$.
Let $c>0$ and $G$ be a graph of chromatic number $\aleph_1$. Are there infinitely many $n$ such that $G$ contains a subgraph on $n$ vertices which cannot be made bipartite by deleting at most $cn$ edges?
Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82].
Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.
Conjectured by Erdős and Gallai. The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.