32 problems

Let $G$ be a connected finite simple graph. A finite planar cover of $G$ is a finite graph that covers $G$ in the graph-theoretic sense, with the covering graph planar. Negami's Pl…

A Hamilton cover of a graph $G$ is a collection of Hamilton cycles whose union contains all edges of $G$. Its size is at least $\left\lceil \frac{\Delta(G)}{2}\right\rceil$, where…

For every graph $H$, consider the problem $\textsc{H-Cover}$ of deciding whether an input graph covers $H$. Strong Dichotomy Conjecture. For every graph $H$, the problem…

The stronger-graph conjecture. If $A$ has no semi-edges and no loops, then

Let $G=G_{n,p}$ be the random graph with $n$ vertices and edge-probability $p$, let $calpha(G)$ denote its independence number, and let $\overline{\theta}_1(G)$ denote the minimum…

Let $G$ be an $n$-vertex $(2k+1)$-regular graph, where $k$ is a nonnegative integer. Let $\operatorname{f_{re}}(G)$ denote the minimum number of $2$-regular graphs and edges in a c…

Let $G$ be an $n$-vertex graph. A cycle-and-edge cover is a cover of the edge set of $G$ by subgraphs that are $2$-regular graphs or single edges. The linear cycle-and-edge cover c…

Let $T$ be a tree of maximum degree $\Delta$. For $d\geq\Delta$, let $\overline{T_d}$ be a $d$-regular graph obtained from $T$ by adding semi-edges or loops so that every vertex of…

Let $H$) be a graph. The problem $\textsc{H-Cover}$ asks whether a given graph $G$ covers $H$. Suppose that $H$ has a finite planar cover. Planar-input conjecture. The…

Let $\mathsf{N}$ be a double-edge normal factor graph (DE-NFG). For each integer $M\geq 1$, let $Z_{\mathrm{B},M}(\mathsf{N})$ denote the degree-$M$ Bethe partition function, defin…

Block reduction conjecture. The problem ${\sc H\text{-}Cover}$ for simple input graphs polynomially reduces to ${\sc H'\text{-}Cover}$ for simple input graphs.

Strong dichotomy conjecture. For every graph $H$, the ${\sc H\text{-}Cover}$ problem is either polynomial-time solvable for arbitrary input graphs, or it is NP-complete for simple…

Linear domination conjecture. There exists a constant $c>0$ such that for every $k$-fold cover $G$ of a graph $F$,

View a graph from model (R1') as a random $n$-cover of a bouquet, the one-vertex multigraph with $d$ self-loops. Hall–Puder–Sawin's conjecture. Their proof should work in this sett…

Graph-cover characterization conjecture. It holds that

Let $\Sigma$ be a connected compact surface without boundary and let $g$ be its Euler genus. A finite $\Sigma$-cover is a finite cover of a connected graph that embeds in $\Sigma$.…

Let $\Sigma$ be an orientable surface of Euler genus $g$, and let a finite $\Sigma$-cover mean a finite cover of a connected graph that embeds in $\Sigma$. Orientable higher-genus…

Let $\Sigma$ be a connected compact non-orientable surface without boundary. A finite $\Sigma$-cover is a finite cover of a connected graph that embeds in $\Sigma$. Hliněný's conje…

Buchanan–Clifton–Culver–Nie–O'Neill–Rombach–Yin conjecture. For every odd positive integer $n$,

Nonexistence conjecture. There is no planar semi-cover $G'$ of $K_{1,2, 2, 2}$ having the properties listed in Lemma $$ .

A signed graph is coverable if it admits a signed circuit cover. A signed circuit $k$-cover is a family of signed circuits in which every edge is covered exactly $k$ times. Fan's c…

Let $G_k$ be the complete multipartite graph with $k$ parts, each of size $2$. For a graph $G$, let $D_r^t(G)$ denote the least integer $d$ such that every $r$-coloring of its edge…

Let $\Gha$ be a vertex transitive graph with a partite presentation $P$ such that $\Gha=\operatorname{PCay}(P)$, and let $\Gpa\leq\operatorname{Aut}_{c\text{-}loc}(\Gha)$ be a tran…

Let $B$ be a $d$-regular graph and let $\{\mathcal{C}_n(B)\}_{n\in N}$ be one of the basic models over $B$, with tangle power $\tau_{\rm tang}$ and algebraic power $\tau_{\rm alg}$…

Let $B$ be a $d$-regular graph, and let $\{\mathcal{C}_n(B)\}_{n\in N}$ be an algebraic model of tangle power $\tau_{\rm tang}$ and algebraic power $\tau_{\rm alg}$. For…