22 problems

A planar semi-cover of $K_{2,2,2,1}$ is a planar graph $G'$ equipped with the projection structure described in the paper. Suppose $G'$ satisfies the following conditions: if…

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…

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…

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…

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.

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

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…

Containment conjecture.

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

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

Cover inequality. Then

Local track-number conjecture. The local track-number of $G$ is at most $3$.

Let $G=(V,E)$ be a finite bipartite graph, let $\tilde{G}$ be its $M$-cover, and let $p(G)=\sum_{I\text{ independent}}\prod_{v\in I}x_v$ be its multivariate independent-set polynom…

Let $\boldsymbol{\theta}$ be a matrix of indeterminates, let $M\in\mathbb{Z}_{>0}$, and let $\tilde{\Psi}_M$ be the set of degree-$M$ graph-covering permutations. For…

Let $\boldsymbol{\theta}$ be a non-negative $n\times n$ matrix. For $M\in\mathbb{Z}_{>0}$, let $\tilde{\Psi}_M$ be the set of degree-$M$ graph-covering permutations and let…