66 problems

TxGraffiti's conjecture. One has

Let $G$ be a $d$-regular graph on $n$ vertices, let $H$ be a spanning subgraph of $G$, and suppose that $d=o(n)$. For each $k\in\{0,1,\dots,d\}$, write $\#\{v\in V(H):d_H(v)=k\}$ f…

Let $n$ be a positive integer, and let $\ell\geq 2$ be fixed. Consider graphs on $2n+1$ vertices, and say that two vertices are joined by a path of length $2\ell+1$ when such a pat…

Let $D$ be a strongly connected digraph on $n$ 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…

Leaf-to-leaf path length conjecture.

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

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…

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…

For each positive integer $n$, let $a_n$ denote the number of bipartite graphical degree sequences on two parts of size $n$, written as $n+n$ vertices. Log-convexity conjecture. Th…

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

Let $\pi_1$ be a graphic degree sequence, and let $\mathbf{k}$ denote the degree sequence in which every term is $k$. Two graphic degree sequences pack when they have realizations…

Ilić–Stevanović's conjecture. The Volkmann tree has maximum spectral moment

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…

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…

Let $n,k∈\mathbb{N}$ with $k≤n$. Let $G$ be an $n$-vertex graph whose degree sequence is $d_1≥⋯≥d_n$. Let an equitable $k$-coloring be a proper $k$-coloring whose color classes hav…

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…

Let $n\in\mathbb{N}$, let $d_1\ge d_2\ge\dots\ge d_n\ge1$ be integers, and let $h$ be a positive integer. The labelled h-factor is … where each tuple denotes the complete graph on…

Let $n\ge 3$ be an integer, and let $(d_1^1,\ldots,d_n^1)$ and $(d_1^2,\ldots,d_n^2)$ be graphic sequences with $d_n^1,d_n^2\ge 1$. Two graphic sequences pack when there are edge-d…

A graphical sequence is planar graphical if it is the degree sequence of a planar graph. Using the shorthand $a^bc^d$ for $b$ repetitions of $a$ followed by $d$ repetitions of $c$,…

Let $G$ be a strongly connected digraph on $n\geq 3$ vertices, and let $d^+_1\leq\cdots\leq d^+_n$ and $d^-_1\leq\cdots\leq d^-_n$ be its ordered outdegree and indegree sequences.…

Odd-length extremal conjecture. For any odd integer $\ell\geq 3$ and sufficiently large $n$, it holds that

Let $\mathcal{G}(n,\Delta)$ be the set of connected nonregular graphs of order $n$ with maximum degree $\Delta$ that attain the maximum spectral radius. Suppose $\Delta\geq 3$ and…

Let $G$ be a $d$-regular graph of order $n$, and let $m(H,k)$ denote the number of vertices of degree $k$ in a spanning subgraph $H$. Asymptotic degree-balance conjecture. For ever…