113 problems

TxGraffiti's conjecture. One has

Let $G$ be a $d$-regular graph with $n$ vertices. A spanning subgraph $H$ has $m(H,i)$ vertices of degree $i$ in $H$, for each $0\le i\le d$. Alon–Wei conjecture. There exists a sp…

Let $H$ be a hypergraph with a prescribed degree sequence, and consider the switch Markov chain on the realizations of that degree sequence, whose transitions apply switch operatio…

Let $D_1,D_2,\ldots$ be an infinite sequence of graphic sequences. For graphic sequences $D_1$ and $D_2$, write $D_1\leq D_2$ if there exist graphs $G_1$ and $G_2$ realizing them s…

For a graph $G$, define … and let $g(n,d)$ be the smallest integer such that every $n$-vertex graph $G$ with $\eta(G)\geq g(n,d)$ is $d$-rigid. Degree-sum conjecture. If…

Leaf-to-leaf path length conjecture.

Magnant–Wang–Yuan's conjecture. The path-cover number satisfies

Let $\mathbf{d}_n$ be a graphic degree sequence, and let $G^P_{\mathbf{d}_n}$ be the final graph of the $\mathbf{d}_n$-process conditioned on having degree sequence $\mathbf{d}_n$.…

Let $d_1\leq\dots\leq d_n$ be the degree sequence of a graph $G$. The degree-sequence conjecture. There is a function $f$ such that, for every $\beta>0$, every integer $r\geq 2$, a…

Let $(d_1,d_2,\ldots,d_n)$ be an integer sequence with … where $n>2r$ and $r\geq 3$. A hypergraph is $r$-Hamiltonian if it remains Hamiltonian after the deletion of any set of fewe…

Hamilton decomposition conjecture for strongly balanced degree sequences. The random graph $G_{n,{\bf d}}$ has property $\mathcal{A}_k$ with high probability.

Balogh, Kostochka and Treglown's conjecture. Then $G$ contains a perfect $K_r$-tiling, that is, a collection of vertex-disjoint copies of $K_r$ covering all vertices of $G$.

Let $n,r\in\mathbb{N}$ with $r$ dividing $n$, and let $G$ be a graph on $n$ vertices whose degree sequence is $d_1\leq\cdots\leq d_n$. Balogh–Kostochka–Treglown conjecture. If … fo…

Let $\pi=(d_0,d_1,\ldots,d_{k-1},1,\ldots,1)$ be a graphic unicyclic degree sequence with $2\le d_0\le d_1\le\ldots\le d_{k-1}$ and $d_k=\ldots=d_{n-1}=1$. Let $\mathcal{U}_{\pi}$…

Bauer et al.'s conjecture. Determining $\alpha_{\min}(d)$ is computationally hard. The same computational hardness is believed to hold for determining $\gamma_{\max}(d)$, where…

Let $G_n$ denote the graph property of containing a $k$-factor, and let $f(k,n)$ be the number of $k$-factor sinks in $G_n$. A weakly optimal Chvátal-type condition is a condition…

Erdős–Jacobson–Lehel conjecture. For every integer $t\geq 3$,

Let $k\geq2$, $s\geq1$, $1\leq r\leq k-1$, and let $p\geq1$ be real. Suppose that … If $\mathcal F\subseteq\binom{[n]}k$ satisfies $\nu(\mathcal F)\leq s$, let $\mathcal B_S$ denot…

Let $1\leq t\leq k$, $1\leq r\leq k-1$, and let $p\geq2$ be real. Suppose that … If $\mathcal F\subseteq\binom{[n]}k$ is $t$-intersecting, then, for every $T\in\binom{[n]}t$, defin…

For positive integers $\ell$ and $n$, let $p_\ell(n)$ denote the maximum number of edges in an $n$-vertex graph containing no two vertices of equal degree connected by a path of le…

Let $m$ be the number of edges, let $n_0(\mathcal D)$ denote the number of vertices of degree zero, let $m^{\neq 2}$ denote the number of edges incident to vertices whose degrees a…

Let $D$ be a digraph on $n\geq 3$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash-Williams' di…

Brualdi's and Busch–Ferrera–Hartke–Jacobsen–Kaul–West's conjecture. The sequence $\pi$ admits a realization containing $h$ pairwise disjoint perfect matchings if and only if…

Briggs, McDonald, and Shan's conjecture. The sequence $\pi$ is $H_h$-realizable if and only if $\sum_{i=1}^n d_i$ is even, $n$ is a multiple of $h+1$, and, for every $k\in[n]$,

Shteiner–Shteyner's conjecture. If $G=(V,E)$ is bipartite, then