126 problems

All graphs under consideration are finite and simple. For a graph $G$ and a vertex $v$, let $d_G(v)$ denote the degree of $v$. Dean's conjecture. For every integer $k \ge 3$, every…

For every infinite arithmetic progression $P\subseteq\mathbb{N}$ with positive common difference that contains an even number, does there exist a constant $c=c(P)\in\mathbb{Q}$ suc…

Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that - $H_1$ has $\gg \delta^3n^2$ edges and every two edges in $H_1$ a…

Let $h(n)$ be minimal such that there is a graph on $n$ vertices with $n+h(n)$ edges which contains a cycle on $k$ vertices, for all $3\leq k\leq n$. Estimate $h(n)$. In particular…

If a graph $G$ has girth greater than $4$, can its edges always be oriented so that the orientation contains no directed cycle and no cycle becomes directed after reversing the ori…

For $k≥4$, let $f_k(n)$ be the largest possible odd girth of a $k$-chromatic graph on $n$ vertices. Is $f_k(n)$ bounded above and below by positive constants times $n^{1/(k-2)}$?

Does every graph with $n$ vertices and $2n-2$ edges contain a cycle and a vertex outside that cycle which is adjacent to three vertices on the cycle?

For every integer $s≥2$, is there a constant $c_s>0$ such that every graph of minimum degree at least $k$ and girth greater than $2s$ contains more than $c_sk^s$ cycles of distinct…

Let $f(n)$ be the maximal number of edges in a graph on $n$ vertices such that all cycles have more vertices than diagonals. Is it true that $f(n)\ll n$?

Let $k\geq 4$ and $g_k(n)$ denote the largest $m$ such that there is a graph on $n$ vertices with chromatic number $k$ and girth $>m$ (i.e. contains no cycle of length $\leq m$). D…

What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?

Any graph on $n$ vertices can be decomposed into $O(n)$ many edge-disjoint cycles and edges.

Given any function $f(n)→∞$, is there a graph $G$ with chromatic number $ℵ_1$ such that, if $g_G(n)$ is the least number of vertices in an $n$-chromatic subgraph of $G$, then…

For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number…

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

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…

Does there exist a zero-density set $A$ of positive integers and a constant $c(A)$ such that every sufficiently large graph with average degree at least $2c(A)$ contains a cycle wh…

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 it true that $\sum\frac{1}{a_i}\gg \log k?$ Is the sum…

Every finite simple graph $G=(V,E)$ with minimum degree at least $3$ contains a cycle of length $2^k$ for some natural number $k$ with $k\geq 2$.

Must every graph of infinite chromatic number contain cycles of length $2^n$ for infinitely many integers $n$?

Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?

If a graph $G$ contains odd cycles of at most $k$ different lengths, must $\chi(G)\leq2k+2$, with equality only when $G$ contains $K_{2k+2}$?

If an infinite graph has infinite chromatic number and $a_1<a_2<…$ are the lengths of its odd cycles, must $Σ_i 1/a_i$ diverge?

A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every $n$-vertex graph has a decomposition into $O(n)$ cyc…

For a digraph $D$, its minimum out-degree is the minimum number of outgoing edges over all vertices of $D$. Lichiardopol's conjecture. For every $k\geq1$, there exists an integer…