32 problems

For a digraph $G$, let $\operatorname{girth}(G)$ be the length of a shortest directed cycle. Define $\beta(G)$ to be the least number of arcs whose deletion makes $G$ acyclic, and…

Dross–Montassier–Pinlou conjecture. Every planar graph $G$ of girth at least $g$ satisfies

Let $\mathcal H\subseteq\binom{[n]}{k}$ be a $k$-uniform hypergraph, and let $\mathcal C\subseteq\mathcal H$ be an even cover if $\mathcal C$ is nonempty and every vertex lies in a…

Dobson's conjecture. If

For a graph $G$, write $\chi(G)$ for its chromatic number and $\operatorname{girth}(G)$ for its girth. Erdős's conjecture. Given any two natural numbers $g,r\geq 2$, there exists a…

Let $G$ be a graph on $n$ vertices with $m$ edges, and let $\alpha_1(G)$ denote the order of a largest induced $1$-degenerate subgraph of $G$, equivalently a largest induced forest…

Planar girth fractional-domatic conjecture. For every integer $k\ge 1$, if $3k-1\le g\le 3k+1$, then

Let $D(k,q)$ be the graph defined by the parameters $k$ and the prime power $q$. Lazebnik–Ustimenko–Woldar's conjecture. For every prime power $q\ge 4$, the graph has girth … The s…

Let $\ell$ and $k$ be positive integers, let $G$ be a graph, and let $T$ be a tree with $k$ edges. Write $\delta(G)$ and $\Delta(G)$ for the minimum and maximum degrees of $G$, and…

For a graph $F$ with at least one edge, let $\chi(F)$, $\omega(F)$, and $\operatorname{girth}(F)$ denote its chromatic number, clique number, and girth. The cited theorem asserts t…

Let $G$ be a bipartite digraph with bipartition $(A,B)$, and let $\operatorname{girth}(G)$ denote its directed girth. Seymour–Spirkl conjecture. If $k$ is a positive integer,…

Let $g\in\mathbb{N}$. A graph has the AOP property if it admits an acyclic orientation with at most one directed path between any pair of vertices, and its girth is the length of i…

Let an irreducible snark be a snark for which deleting any pair of distinct vertices produces a $3$-edge-colourable graph, and let the girth of a graph be the length of its shortes…

Let $G$ be a graph in the setting of the paper's cop-number upper bound, with minimum degree $\delta$ and order $n$. Extension conjecture. The same upper bound holds for graphs wit…

Let $d$ and $g$ be positive parameters. Folklore regular-graph girth conjecture. There exist $d$-regular graphs of girth $g$ and order … This folklore conjecture is cited as suppor…

Let $X$ be an arbitrary connected graph with finite girth, and let $\mathcal C$ be the set of cycle subgraphs in $\mathsf{FS}(X,\operatorname{Star}_n)$ that achieve its girth. For…

Let $\mathcal G$ be the set of simple graphs whose friends-and-strangers graph with a star factor has the relevant girth property, and let $\tilde{\mathcal G}$ be the explicitly de…

Girth analogue conjecture. For every graph $F$ with at least one cycle, there exists a constant $b_F$ and graphs $G$ of arbitrarily large chromatic number and the same girth as $F$…

Girth conjecture for $BS_6$. For every $n\geqslant 19$,

Let $X$ be a connected graph with finite girth, let $\mathcal C$ be the set of cycle subgraphs of $\mathsf{FS}(X,\textsf{Star}_n)$ that achieve its girth, and for each…

For a ring or field … be the bipartite graph whose two partite sets are copies of $^3$, with $(a_1,a_2,a_3)$ adjacent to $[x_1,x_2,x_3]$ exactly when … and … For a finite field … .…

Let $G$ be a planar graph of girth at least five, and let $\fva(G)$ denote its fractional vertex-arboricity. Fractional Kowalik–Luv{z}ar–Škrekovski conjecture. Every planar graph o…

Let $k$ be a positive integer and let $g\ge3$ be an integer. For a graph, its chromatic number is denoted by $\chi(G)$, its average degree is the average of its vertex degrees, and…

Let $x\ge1$ be real and let $g\ge3$ be an integer. For a graph $G$, let $\chi_f(G)$ denote its fractional chromatic number, and let the girth of a graph be the length of its shorte…

Let $d_0$ and $g_0$ be constants. A bipartite induced subgraph is an induced subgraph that is bipartite. Girth-induced-subgraph conjecture. There exist $d_0$ and $g_0$ such that an…