48 problems

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

Let $\mathcal{G}_5$ be the class of planar graphs of girth at least $5$, and let $n$ denote the order of such a graph. An induced forest is an induced subgraph that is a forest. Ko…

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…

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

Let $\chi_f”(G)$ denote the fractional total chromatic number. Reed's conjecture. For every $\epsilon>0$ and every maximum degree $\Delta$, there exists a girth $g$ such that every…

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…

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

For a set $\mathcal{F}$ of graphs, let $ex(n;\mathcal{F})$ denote the maximum number of edges in a graph of order $n$ that contains no member of $\mathcal{F}$ as a subgraph. In par…

Let $k$ be a positive integer, and let ${\mathcal C}_{\leq 2k}$ denote the family of all cycles of length at most $2k$. The Erdős girth conjecture. There is a constant $c(k)>0$ suc…

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 $f(n,m)$ be the maximum number of edges in a bipartite graph whose two parts have sizes $n\ge m$, subject to girth at least eight. Erdős's conjecture. If $m=O(n^{2/3})$, then ……

Let a KT orientation be an orientation $D$ of a graph such that, for every pair of vertices $u,v\in V(D)$, there is at most one directed path with $u$ and $v$ as its ends. A graph…

Even-cycle high-girth extremal bound conjecture. This upper bound is tight up to a constant factor; the conjecture holds for $\ell\in\{2,3,5\}$.

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

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(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 $G$ be a planar graph with girth at least $4$ and maximum degree $Delta$. The girth-four 2-distance coloring conjecture. asserts … and … The source motivates these bounds by co…

Random large-girth extremal conjecture. There exists $\gamma=\gamma(\ell,r)$ such that, asymptotically almost surely,

Optimal exponent conjecture. For all $r\geq 2$, $\ell\geq 3$, and $m,n\geq 1$,

Large-girth extremal conjecture. For all $\ell \geq 3$ and $r\geq 2$,

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

Erdős's conjecture. There exist Steiner triple systems of arbitrarily large girth.