30 problems

Let $G$ be a finitely generated group, and define its Schreier girth by … where $S$ is a minimal generating set and $S\sim_{\mathcal{S}}S'$ means that $S'$ can be obtained from $S$…

Let $B(G)$ denote the bicircular matroid of a graph $G$, let $U_{t,t+2}$ be the uniform matroid of rank $t$ on $t+2$ elements, and let $M(K_t)$ and $M(K_t)^*$ be respectively the g…

Let $U_{2,q}$ be the $q$-element rank-$2$ uniform matroid, and more generally let $U_{t,q}$ be the $q$-element rank-$t$ uniform matroid. Let $M(K_t)$ be the graphic matroid of the…

Diameter-maximal girth conjecture. If $D$ is odd, then

Algebraic-connectivity monotonicity conjecture. The function $f(g;d,n)$ is increasing as a function of $g$.

Maximum-connectivity–girth conjecture. For fixed degree $d$ and order $n$, a graph maximizing $AC(G)$ also has maximum possible girth.

Large-girth strong arboricity conjecture. For every integer $k$ there is an integer $g(k)$ such that every graph $G$ with

Let $G$ be a planar graph of girth $g\ge5$ and maximum degree $\Delta$. Hudák–Lużar–Soták–Škrekovski conjecture. There exists a constant $C$ such that … The conjecture proposes tha…

Let $G$ be a planar graph of girth at least $5$, and let $\Delta$ be its maximum degree. Dvořák–Kráľ–Nejedlý–Škrekovski conjecture. There exists $\Delta_0$ such that, if…

Let $G$ be a planar graph of girth at least $k$, and let $\Delta$ be its maximum degree. Wang–Lih conjecture. For every $k\ge 5$, there exists $\Delta_k$ such that, if…

Let $g(n)$ denote the largest girth among all cubic graphs on $n$ vertices. Girth bound conjecture. There is a constant $\epsilon_0>0$ such that … The Moore bound gives only…

Let $l,n$ be positive integers. A graph with girth $2l+1$ and $n$ vertices is said to have many edges if its number of edges is bounded below by a positive constant times…

High-girth Nash-Williams conjecture. For every fixed $g$, every sufficiently large $K_3$-divisible graph $G$ with

High-girth triangle-decomposition conjecture. For every fixed $g$, every sufficiently large $K_3$-divisible complete graph $K_n$ has a $K_3$-decomposition with girth at least $g$.

Let $g$ and $d$ be positive integers. A graph is $d$-regular if every vertex has degree $d$, its girth is the length of its shortest cycle, and its order is its number of vertices.…

Let $\rho(d,g)$ denote the maximum Hall ratio among graphs of maximum degree at most $d$ and girth at least $g$. Girth-shifting conjecture. The values presented in the table are up…

An oriented graph is a digraph without 2-cycles. Let $h$ and $g$ be positive integers, and let $l(h,g)$ be the minimum integer such that every oriented graph of girth $g$ and minim…

Let $k$ and $g$ be positive integers, and let $f(k,g)$ be the minimum integer such that every finite simple digraph of girth $g$ and minimum outdegree at least $f(k,g)$ contains…

Strong girth conjecture. For every positive integer $k$, there exists a family of almost-regular graphs $\{G_n\}$ such that $|V(G_n)|=n$, $|E(G_n)|\ge \frac{n^{1+1/k}}{2}$, and…

Large-girth minimum semidefinite rank conjecture. If $G$ has girth at least $k$, then

A Steiner Triple System is a combinatorial design consisting of triples on a vertex set such that every pair of vertices lies in exactly one triple. Its girth is the smallest integ…

Davila–Kenter conjecture.

Feedback vertex set conjecture for prescribed girth. There exists a feedback vertex set $S$ of $G$ satisfying

Kowalik et al.'s conjecture. The graph $G$ admits an induced forest of order at least

The higher-girth face-number conjecture. There is a constant $C_{p,r,i}$ depending only on $p,r,i$ such that