282 problems

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

Multiplicity Ryser-Brualdi-Stein conjecture. There exists a matching $M$ in $G$ such that

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

Let $F_i$, $i\leq k$, be subgraphs of $K_{n,n}$, and let $A=(a_{ij})$ be the $k\times n$ matrix whose entry $a_{ij}$ is the degree of $v_j$ in $F_i$. Let $r_i(A)$ be the sum of the…

The Asymptotic Upper Matching Conjecture. Under these hypotheses,

The Upper Matching Conjecture. One has

The Asymptotic Lower Matching Conjecture. Under these hypotheses,

Let $\{G_k=(V_k,E_k)\}_{k\in\mathbb{N}}$ be a sequence of $r$-regular bipartite graphs with $\#V_k\to\infty$. Let $h_{\{G_k\}}(p)$ denote the associated monomer–dimer entropy, and…

Let $G$ be a bipartite graph. Let $p(G)$ and $\widehat{p}(G)$ denote the minimum numbers of colors in a parity edge-coloring and a strong parity edge-coloring, respectively. The bi…

Let $G$ be a planar bipartite graph, and let $P(G,t)$ be its chromatic polynomial. Let $\tau=(1+\sqrt{5})/2$ be the golden ratio. Salas–Sokal conjecture. … Equivalently, planar bip…

Let $T_{a,b}=(A,B)$ be a tree whose bipartition satisfies … For a bipartite graph $H$, let $\operatorname{ex}_{\mathrm{bip}}(m,n;H)$ be the maximum number of edges in an $H$-free b…

Every tree is bipartite. Write $T_{a,b}=(A,B)$ when the two parts of $T$ satisfy … For a bipartite graph $H$, let $\operatorname{ex}_{\mathrm{bip}}(N;H)$ be the maximum number of e…

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

Akiyama–Watanabe–Albertson–Hass conjecture. Every bipartite planar graph $G$ satisfies

Let $G$ be a bipartite graph, and let $\Delta(G)$ denote its maximum degree. Alon's conjecture. There exists a constant $c$ such that … This conjecture concerns whether bipartite g…

Let $H$ be a fixed bipartite graph. For positive integers $n,m$, let $N_{\mathrm{bip}}(n,m,H)$ be the maximum number of unlabelled copies of $H$ over bipartite graphs $G$ with…

Unbalanced bipartite measurable edge-coloring conjecture. For every probability measure $\mu$ on $V$,

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

Asymptotic extremal-number conjecture.

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…

Square-root discrepancy conjecture. There is a perfect matching $M$ of $K_{n,n}$ satisfying

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…

Extension conjecture. Theorems … should hold for $(c,r)$-bounded graphs with $1\le c\le r$.