17 problems

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

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

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

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…

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…

Thomassen's conjecture. There is a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that, for all $t,k\in\mathbb{N}$, every bipartite graph of average degree at least $f(t,k)$ h…

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…

Let $H$ and $H'$ be ordered forests, and let $t$ be a positive integer. Write $R_<(H,H')$ for the family of Ramsey graphs of $(H,H')$, and let $\operatorname{girth}(F)$ denote the…

A feedback vertex set of a graph $G$ is a set $S\subseteq V(G)$ such that $G-S$ is a forest. Let $\phi(G)$ denote the minimum size of a feedback vertex set of $G$. The girth of a g…

Let $G$ be a planar graph of girth at least $3k+2$ with $n$ vertices, and let $\gamma'_R(G)$ denote its edge Roman domination number: the minimum of $\sum_{e\in E(G)}f(e)$ over all…