170 problems

Alon–Krivelevich–Sudakov conjecture. The condition

Let $G$ be a graph, and let $k\geq 2$ be an integer. A collection of $k$ spanning trees of $G$ is called a collection of completely independent spanning trees if, for every pair of…

Let $G$ be a connected graph, let $cs0(G;\mathbf{x})$ be the spanning-tree sum … where $\mathcal{T}(G)$ is the set of spanning trees of $G$ and $\mathbf{x}\in\mathbb{F}_q^{E(G)}$ a…

Thin tree conjecture. Every $k$-edge-connected graph contains a spanning tree whose thinness is $o(k)$.

Let $X_1,X_2$ and $X_3$ be the partite sets of the complete tripartite graph $K_{n_1,n_2,n_3}$, where $|X_i|=n_i$ for $i\in \llbracket 3\rrbracket$. Let $F$ be a spanning forest in…

Let $K_n$ be a complete graph and let a $1$-factorization be an edge-colouring whose colour classes form a decomposition of $K_n$ into perfect matchings. A subgraph is rainbow if a…

Let $G$ be a regular graph. A spanning even tree of $G$ is a spanning tree in which every vertex has even degree. Jackson–Yoshimoto conjecture. Every connected non-bipartite regula…

Grünbaum's conjecture. Every planar 3-connected graph $G$ contains a 3-tree $T$ whose co-tree $\neg T^*$ is also a 3-tree.

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

A triangulation of the sphere is a triangulation of the 2-sphere, and its minimum degree is the smallest vertex degree in its graph. A HIST is a homeomorphically irreducible spanni…

A balanced partition is a partition of the vertices of a grid into connected pieces whose weights are approximately equal. Charikar–Liu–Liu–Vuong conjecture. In the case of grids,…

A $k$-graph is a hypergraph whose edges have size $k$. It is linear if every pair of distinct edges shares at most one vertex, and a loose hypertree is a connected linear $k$-graph…

Let $d\geq 1$, let $G$ be a $d$-vertex-connected graph, and let $r$ be a vertex of $G$. A family of spanning trees $T_1,\ldots,T_d$ is said to provide independent paths from $r$ if…

Let $G$ be a $k$-vertex-connected graph, and let $r$ be any root of $G$. A collection of spanning trees $T_1,\dots,T_k$ is independent with root $r$ if, for every vertex…

Let $k$ and $r$ be integers with $r\geq 2k\geq 4$, and let $G$ be an $r$-regular connected graph. Write $\lambda_2(G)$ for the second-largest adjacency eigenvalue and $\tau(G)$ for…

Let $G$ be a connected graph. Its density is … The graph $G$ is uniformly dense if $d(H)\leq d(G)$ for every connected subgraph $H$ of $G$. A graph is cyclically orderable if it ha…

Let $\mu(n)$ be the maximum number of spanning trees of a planar multigraph with $n$ edges. Let … be Catalan's constant, and set $\mathcal C=e^{2C/\pi}$. Catalan-constant upper-bou…

Ferrers bound conjecture. Every such graph satisfies

Let $G$ be a $2$-connected cubic graph of order $n$. The minimum leaf number $ml(G)$ is the minimum number of leaves among the spanning trees of $G$. Minimum leaf number conjecture…

Frieze–Krivelevich conjecture. There exists a constant $\alpha>0$ such that every globally $\alpha n$-bounded coloring contains any spanning tree with bounded maximum degree.

For $3\leq k\leq 6$, let $\mathcal{X}_{n,k,g}$ be the class of graphs considered in the source and define … where $g$ is fixed sufficiently large and $\tau(G)$ is the number of spa…

Let $G$ be a simple graph, and let $\tau(G)$ denote its number of spanning trees. A $k$-regular graph of girth $g$ with the minimum possible number of vertices is called a $(k,g)$-…

Let $N_\varepsilon(\mathcal F)$ denote the number of points of branching of scale $\varepsilon$ in a scaling-limit spanning-tree configuration $\mathcal F$. The branching number of…

Conjectured formulas.

Let $G$ be the infinite nearest-neighbor graph on the integer lattice in $d$ dimensions, and let ${\bf T}$ be the uniform spanning forest obtained as a distributional limit of unif…