148 problems

Let $G$) be a connected $d$-regular graph with adjacency matrix $A$ and $n$ vertices. Let $\xi_1,\xi_2,\ldots,\xi_n$ be orthogonal eigenvectors of $A$, with the conditions stated b…

Nonexistence conjecture. There are no $8$-regular $K_3$-irregular graphs.

A subgraph $H\leq G$ of a graph $G$ is a graph $H=(V,E)$ such that $V\subseteq V(G)$ and $E\subseteq E(G)$. A graph is $k$-regular if every vertex has degree $k$. Berge-Sauer conje…

Regular Boesch conjecture. If an $(n,kn/2)$ UMRG exists and has girth $g$, then it has maximum girth among all $k$-regular $(n,kn/2)$-graphs and, among the $k$-regular $(n,kn/2)$-g…

Regular extremal-structure conjecture. For every integer $d\ge3$, there exist constants $C_1$ and $C_2$ such that any $\mu$-minimal $d$-regular graph $G$ of order at least $C_1$ is…

Let $d$-regular graphs be graphs in which every vertex has degree $d$, and call a partition of the vertex set into two parts an internal partition when every vertex has at least as…

Sheehan's conjecture. There is no finite $r$-regular graph with a unique Hamilton cycle for any $r>2$.

Let $G$ be a vertex-regular planar graph, and suppose that all but two faces of $G$ have the same degree. Nearly platonic graph conjecture. The remaining two faces must have the sa…

Mkrtchyan–Petrosyan–Vardanyan conjecture. If

Let $G$ be a simple graph, and let $\tau(G)$ denote its number of spanning trees. A $k$-regular graph of girth $g$ with the minimum possible number of vertices is called a $(k,g)$-…

Let $(H,\Phi)$ be a standard pairing, where $H$ is a finite connected regular graph and $G(\Phi)^*$ denotes the graph associated with the pairing after removing singular components…

Asymptotic domatic-number conjecture. For every fixed real number $C\geq 1$,

Let $\mathcal{G}_{n,d}$ be the uniform model of random $d$-regular graphs on the vertex set $[n]=\{1,2,\ldots,n\}$. A $p$-orientation is an orientation of a $d$-regular graph in wh…

Let $\varepsilon>0$ be real. There is a constant $d_{\varepsilon}>0$ such that for every integer $d\geq d_{\varepsilon}$, every connected $n$-vertex $d$-regular graph $G$, and a un…

Let $n,d\geq 3$ be integers, and let $G$ be a connected $n$-vertex $d$-regular graph. Write $T_{\mathrm{unlabeled}}(G)$ for the set of isomorphism classes of spanning trees of $G$.…

Existence conjecture. For every permitted degree $d$ in the two displayed sets, the corresponding regular open or closed XOR-magic graph exists. This would complete the existence p…

Given graphs $F$ and $G$, a subdivision packing of $F$ in $G$ is a collection of pairwise vertex-disjoint copies of subdivisions of $F$. For a real number $\eta > 0$ and a graph…

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 a $6$-regular graph. A 2-factor is a spanning $2$-regular subgraph, and a component of a $2$-factor is one of its connected components. The 6-regular three-2-factor conj…

Let $n$ and $d$ be integers with $1\leq d\leq n-2$ and $dn$ even, and set $\lambda=d/(n-1)$ and $\varLambda=\lambda(1-\lambda)$. Let $\operatorname{RG}(n,d)$ denote the number of…

Let $G$ be a directed $d$-regular graph on $n$ vertices, and regard a cycle as a directed cycle, with an individual edge allowed to count as a cycle of length two as in the source.…

Let $G$ be an $n$-vertex $d$-regular graph, and let $F \sim G_{n,2}$ be a uniformly random 2-factor, that is, a spanning 2-regular graph, on the same vertex set. Draganić–Keevash c…

Let $G$ be a graph on $n$ vertices. It is link-irregular if $G[N(u)]$ and $G[N(v)]$ are non-isomorphic for every pair of distinct vertices $u,v$, where $N(u)$ denotes the neighborh…

Let $\mathcal{G}_{n,3}$ be the random $3$-regular graph on $n$ vertices, and let $s(G)$ denote the smallest size of a Sudoku set for a graph $G$. Here, a Sudoku set is a vertex sub…

Burris–Schelp conjecture.