282 problems

Let $G$ be a bipartite graph with $n$ vertices. The minimum distance signless Laplacian spread conjecture. … Equality holds if and only if … This proposes that the balanced complet…

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$, and let $i\leq p$ and $j\leq q$. Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic…

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 $G$ be an $(a,b)$-bipartite graph, meaning that the two vertex classes of $G$ have maximum degrees at most $a$ and $b$, respectively. Brualdi–Quinn Massey's conjecture. The str…

Alon–Krivelevich conjecture. There is an absolute constant $C$ such that

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 $G$ be a bipartite graph, let $d_u$ denote the degree of $u\in V(G)$, and let $H$ be a loop-graph. Write $\hom(G,H)$ for the number of graph homomorphisms from $G$ to $H$. Galv…

Let $H$ be a bipartite graph, and let $\widetilde{T}_H(x,y)$ denote its normalized Tutte polynomial. Assume that every vertex of $H$ has degree at least $2$. Merino–Welsh conjectur…

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

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

Thomassen's conjecture. There is a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that, for all $t,k\in\mathbb{N}$, every bipartite graph of average degree at least $f(t,k)$ h…

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each part, and suppose its edges are partitioned into sets $E_1,\ldots,E_m$, where $m\leqslant n$. A perfect matc…

Faudree–Schelp–Gyárfás–Tuza conjecture. The following bounds hold:

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

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…

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…

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…

Let $H$ be a bipartite graph, let $M_H(n)$ denote the maximum running time of the $H$-process, and let $\operatorname{ex}(n,H)$ be the Turán extremal number of $H$. Bipartite extre…

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

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

Kostochka et al.'s conjecture. If a bigraph $G=(X,Y)$ is snp, then there is a cycle containing all vertices of $X$.

Let $G$ be a bipartite graph of size $m$ with bipartition sets $S$ and $T$, satisfying $2\leqslant |S|\leqslant |T|$ and $0<m<|S||T|$. A graph achieves the maximum spectral radius…

Let $G$ be a finite connected graph, possibly with multiple edges but no loops. A spanning tree $T$ of $G$ is even if all leaves of $T$ belong to the same part of the bipartition o…

Let $G$ be a $2$-factor Hamiltonian $k$-regular bipartite graph, meaning that every $2$-factor of $G$ is a Hamiltonian circuit. Sheehan's conjecture. There are no $2$-factor Hamilt…

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