421 problems

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

Jackson's conjecture. Every regular bipartite tournament has a Hamilton decomposition.

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

Brualdi–Quinn Massey conjecture. For any bipartite graph $G$ with partite sets $A$ and $B$,

Let $G$ be a bipartite graph, and let $4\chi_\ell(G)4$ denote its list chromatic number and $4\Delta(G)4$ its maximum degree. Alon–Krivelevich conjecture. The list chromatic number…

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…

For positive integers $s,t e 1$, let ${rm ex}(n,K{s,t})$ denote the maximum number of edges in an $n$-vertex graph containing no copy of $K{s,t}$. The source records the bound … fo…

Graham–Häggkvist conjecture. The edge set of $K_{n,n}$ can be decomposed into copies of every $n$-edge tree $T$.

For positive integers $n,s$, let $K_{s,s}$ be the complete bipartite graph with $s$ vertices in each part. For a graph $H$, let $\mathrm{ex}(n,H)$ be the maximum number of edges in…

Luo–Tian–Wu's conjecture. Every $\k$-connected bipartite graph $\G$ with

Let $d$ be a positive real number, and let $G$ be a triangle-free graph with minimum degree at least $d$. An induced bipartite subgraph of $G$ is a bipartite subgraph induced by a…

Let $T_1,\dots,T_n$ be trees such that, for each $i\in[n]$, $T_i$ has $i$ vertices. Define … A decomposition of $G$ into $T_1,\dots,T_n$ is a collection of pairwise edge-disjoint c…

Let $G$ be a $d$-regular bipartite graph on $v(G)$ vertices, and let $m_k(G)$ denote the number of matchings of size $k$. Set $p=2k/v(G)$, and let $\mathbb{G}_d(p)$ denote the stat…

Let $G$ be a $K_4$-free graph on $n$ vertices. The Balogh–Clemen–Lidický conjecture. $G$ can be made balanced bipartite by removing at most … edges. This conjecture asks whether th…

Salia's conjecture. If $G$ has the double Hall property, then for every $X\subseteq A$ with $|X|\geq 2$ there is a cycle $C_X$ in $G$ such that

Let $K_{n,n}$ and $K_{s,t}$ be complete bipartite graphs, with $s$ and $t$ fixed. Moshkovitz–Shapira conjecture. For sufficiently large $n$, … This conjecture concerns the asymptot…

Let $G$ be a bipartite graph of even order, with nonnegative vertex weights, and consider the graph-grabbing game in which Alice moves first and vertices are removed while the rema…

For positive integers $n$, $m$, and $\delta$ with $\delta\leq m$, let $G(n,m,\delta)$ be the set of all bipartite graphs with sides $X$ and $Y$ such that $|X|=n\geq 2$, $|Y|=m$, an…

Minimum-order conjecture. The minimum number of vertices of an extremal bipartite graph is $16$.

Narayanan–Sahasrabudhe–Tomon conjecture. When $m=k^2$, the graph $K_{k,k}$ is extremal for the number of different edge sizes of induced subgraphs among bipartite graphs with $m$ e…

Let $t\geq 2$ be an integer, and let $H$ be a $K_{2,t}$-free bipartite graph such that every vertex in one of the parts of $H$ has degree at most $t$. Conlon–Janzer–Lee conjecture.…

Generalized Turán number exponent conjecture. There exists $t_0$ such that, for all $t\geq t_0$,

Let $G$ be a $d$-regular balanced bipartite graph on $2n$ vertices, and let $f4d8^{\mathbf{connect}}_{k,\mathrm{reg}}(n)$ denote the minimum-degree threshold for the $k$-switch gra…

Ehrenborg's conjecture. For every bipartite graph $G$, one has

Bipartiteness conjecture. Every $(k,g)$-cage with even girth $g$ is bipartite.