94 problems

For positive integers $n$ and $t$, let $r(n,t)$ be the maximum number of colors in an edge-coloring of $K_n$ that has no $t$ edge-disjoint rainbow spanning trees. Jahanbekam–West c…

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 $K_k$ be the complete graph on $k$ vertices, let $P_n$ be the path graph on $n$ vertices, and consider the spanning-tree recurrence for the graph product $K_k\times P_n$. Compl…

Kriesell's conjecture. There exists a smallest integer $g(k)$ such that every $g(k)$-connected graph $G$ contains a spanning tree $T$ for which

Let $\mathcal{RS}_n$ be the rainbow-spanning-tree game played on $n-1$ copies of $K_n$, where Maker wins by claiming a rainbow spanning tree, and let $b_{\mathcal{RS}_n}$ denote it…

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

Asymptotic ratio conjecture. The limit exists:

Let $G=(V,E)$ be an unweighted undirected graph. A set $T\subseteq E$ is $\alpha$-thin with respect to $G$ if, for every nonempty set $S\subsetneq V$, … A graph is $d$-edge-connect…

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…

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.

Let $G$ be a connected cubic graph. Hoffmann-Ostenhof's 3-Decomposition Conjecture. $G$ can be decomposed into a spanning tree, a collection of cycles, and a possibly empty matchin…

Let $G$ be a graph and let $v$ be any specified vertex of $G$. A collection of spanning trees of $G$ is independent spanning trees rooted at $v$ if, for every vertex $u$, the paths…

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 with a proper edge-colouring, meaning that any two incident edges have different colours. A subgraph is rainbow if all its edges have distinct colours…

Let $\hat{\mathcal{G}}_{2n+1}$ be the graph whose components $A$ have labeled edges, and let $\eta$ be a label of a component $A$. A component spanning tree of $A$ is a spanning tr…

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

Let $G$ be a finite connected graph, let ${\bf T}$ be a uniform spanning tree, let $e$ be an edge, and let $A$ be an up-event, meaning an upwardly closed event in the space of subg…

Asymptotic growth constant conjecture. The asymptotic growth constant is

Spanning-tree factorization conjecture. The number of spanning trees is

Let $Q_n$ be the $n$-dimensional hypercube and let $F_{n+1}$ be the dual-cube of dimension $n+1$. Let $k$ be a positive integer. Dual-cube lifting conjecture. If $Q_n$ has $k$ comp…

Periodic perfect-power maximality conjecture. Its spanning-tree count is at most

Perfect-power square-maximality conjecture. Equality should occur only for the $d$-dimensional box $P_n^{\square d}$, up to lattice translation and coordinate permutation.