1,505 problems

Let $H$ be a bipartite graph and let $G$ be a graph. Write $v(H)$ and $e(H)$ for the numbers of vertices and edges of $H$, and likewise $v(G)$ and $e(G)$ for $G$. Let $\hom(H,G)$ d…

Let $T$ be a tree on $t$ vertices. For a graph $G$, write $e(G)$ for its number of edges, and call $G$ $T$-free if it contains no subgraph isomorphic to $T$. Erdős–Sós conjecture.…

Let $r,g\in \mathbb{N}$. A digraph $D$ has girth at least $g$ if its shortest directed cycle has length at least $g$, and let $\delta^+(D)$ denote its minimum out-degree. Caccetta–…

Burr–Erdős conjecture. Every $n$-vertex graph without cycles of length $\ell$ modulo $k$ has at most a linear number of edges in $n$.

Let $G$ be a non-complete graph on $n$ vertices with $m$ edges, adjacency eigenvalues $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$, and clique number $\omega=\omega(G)$. Bollobás–N…

Let $K_{a,b}$ be the complete bipartite graph with parts of sizes $a$ and $b$, and let $\operatorname{cr}(K_{a,b})$ denote its crossing number. Zarankiewicz's conjecture. … This is…

Throughout, let $F$ be a graph, and let $\operatorname{Ex}(n,F)$ be the set of $n$-vertex $F$-free graphs maximizing the number of edges, while…

Let $G$ be a graph on $n\geq 3$ vertices, let $r$ be a positive integer, and let $\delta(G)$ denote the minimum degree of $G$. The $r$-th power $\mathcal{C}^r$ of a Hamilton cycle…

Let $d(t)$ be the smallest real number such that every graph with average degree more than $d(t)$ contains a subdivision of $K_t$. Mader–Erdős–Hajnal conjecture. For $t\to\infty$,…

Komlós's conjecture. Every graph $G$ with minimum degree $d$ satisfies

Let $G$ be an outerplanar graph on $n$ vertices, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, let $P_{n-1}$ be the path on $n-1$ vertices, and let $\vee$ de…

Triangle-free process independence-number conjecture. The triangle-free process has asymptotically the smallest independence number among all $n$-vertex triangle-free graphs.

Erdős–Simonovits–Sós conjecture.

Loebl–Komlós–Sós conjecture. If at least $n/2$ vertices of $G$ have degree at least $d$, then $G$ contains a copy of $T$.

Consider graphs with minimum degree at least $3$. Erdős–Gyárfás conjecture. Minimum degree $3$ should suffice to guarantee a cycle whose length is a power of $2$. The source notes…

Verstraëte's conjecture. If $G$ does not contain $k$ cycles of consecutive even lengths, then

Conlon–Lee conjecture. There exists $c=c_H>0$ such that

Conjecture on the 2-connected extremal number.

For a positive integer $k$, let $f(k)$ be the maximum possible chromatic number of a graph whose edge set can be partitioned into at most $k$ complete bipartite graphs, and set…

Pach–Tardos conjecture. The extremal number of $H$ is

Matsumoto's conjecture. For any graph $G$ with $n\geq 4$ vertices,

Davies's conjecture.

Bukh–Conlon conjecture. For any balanced rooted tree $(T,R)$ and any natural number $\ell$, we have

Let $G$ be a planar graph on $n$ vertices, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, let $P_{n-2}$ be the path on $n-2$ vertices, and let $\vee$ denote g…

For an integer $r\geq 5$, let $D_2^\#(K_r)$ denote the maximum number of edges that must be removed to make an $n$-vertex $K_r$-free graph bipartite. Sudakov's conjecture. … The fo…