17 problems

Let $H$ be a graph with a finite planar cover, and let the $H$-Cover problem ask whether a given input graph covers $H$. Planar-input hardness conjecture. Restricting the $H$-Cover…

Let $G=(V,E)$ be a graph, let $\tau(G)$ denote its covering number, and let $L(G)$ be the Laplacian matrix of $G$. For $1\leq i\leq |V|$, write $\lambda_i(L(G))$ for the $i$-th lar…

Asymptotic directed-cycle packing and covering conjecture. For all sufficiently large $n$, every $n$-vertex directed graph $D$ satisfies

McDonald–Puleo–Tennenhouse conjecture.

Angluin's conjecture. The graphs $G$ and $H$ have a common finite cover.

Let two finite graphs have the same degree refinement matrix. Angluin–Gardiner's conjecture. They have a finite common cover. This conjecture extends the proved result that any two…

Let $K_t(d)$ be the complete $t$-partite graph with each part of size $d$. Davoodi–Javadi–Omoomi's conjecture. There exists a function $f$ and a constant $c>0$ such that, for every…

Let $\Gamma$ be a finite connected graph such that the induced action of $\operatorname{Aut}(\Gamma)$ on $H_1(\Gamma;\mathbb Z)$ is faithful, and let…

Let $l\geq 6$ be an integer, and let $\mathcal{C}_{\geq l}$ denote the class of cycles of length at least $l$. For a graph class $\mathcal{H}$, let…

Looped-graph conjecture. Every such $G$ has a one-sided Ramanujan $r$-covering; $\mathcal{M}_{d,G}$ is real-rooted for every $d$; and $G$ has a one-sided Ramanujan $(\Gamma,\pi)$-c…

Loop-extension conjecture. All the results of the paper hold for graphs with loops.

Let $\Gamma$ be an infinite Cayley graph that is not quasi-isometric to $\mathbf Z$. A graph $\Delta$ is a cover of $\Gamma$ if there is a covering map from $\Gamma$ to $\Delta$; w…

Let $\Omega$ be a finite connected graph, let $\Gamma$ be a random $n$-covering of $\Omega$, and let $\lambda_A(\Gamma)$ and $\lambda_M(\Gamma)$ denote the largest absolute values…

Let $K_n$ be a complete graph whose edges are coloured with $r$ colours. A cycle covering is a collection of $r$ monochromatic cycles whose union of vertex sets contains all vertic…

Let $K_n$ be a complete graph whose edges are coloured with $r$ colours. A vertex-disjoint monochromatic cycle packing is a collection of $r$ vertex-disjoint monochromatic cycles.…

Hamilton covering conjecture. For any $p=\omega(\ln n)/n$, the random graph $G(n,p)$ a.a.s. admits a covering of its edges with at most

Balogh's conjecture. Every simple planar graph is $(2,4)$-coverable.