78 problems

Vizing's conjecture. For all graphs $G$ and $H$, one has

Let $G$ be a graph with maximum degree $\Delta(G)$, and let $K_2$ be the complete graph on two vertices. Consider the Cartesian product $G\square K_2$. A precoloring is extendable…

Let $G=(S,E)$ be a subgraph of the Cartesian product … of graphs $G_1,\ldots,G_m$, and let $\operatorname{VC\text{-}dens}(S)$ denote the VC-density of $S$. VC-density conjecture. T…

Let $C_m$ and $C_n$ be cycles with $m,n\geq3$, and let $\mathrm{pmd}(G)$ denote the positive matching decomposition number. Positive matching decomposition conjecture for Cartesian…

Let $\Gamma_1$ and $\Gamma_2$ be graphs, let $\Gamma_1\square\Gamma_2$ denote their Cartesian product, and let $\mathrm{pmd}(\Gamma)$ denote the positive matching decomposition num…

Let $G$ and $H$ be nontrivial, connected graphs. Their Cartesian product $G\mathbin{\Box}H$ is well-dominated if all its maximal independent sets have the same cardinality. Rall's…

Let $P_m$ be the path graph on $m$ vertices and $C_n$ the cycle graph on $n$ vertices, with $m,n\in\mathbb{N}$, $m\geq 2$, and $n\geq 3$. Their Cartesian product $P_m\Box C_n$ is t…

Let $\Gamma(\mathbb{Z}_{2n+1}^n,\mathcal{U})$ be the Cartesian product of $n$ cycles of length $2n+1$, where $2n+1$ is prime, and let $\mathcal{F}$ be the family of all minimum dom…

Fixed-$l$ grid-threshold conjecture. For fixed $l$,

For graphs $F$ and $G$, their Cartesian product $F\Box G$ has vertex set $V(F)\times V(G)$, with $(u,v)$ adjacent to $(u',v')$ if and only if either $u=u'$ and $vv'\in E(G)$, or…

Kao's conjecture. If $n\geq 4\Delta(G)-2$ and $G\Box P_n$ is balanced bipartite, then $G\Box P_n$ is hamiltonian.

Cartesian-product precoloring extension conjecture. This precoloring is extendable to a proper edge coloring.

Let $G$ and $H$ be graphs, and let $\boxempty$ denote the Cartesian product of graphs. A graph is outer-cylindrical (OC) if it has a planar embedding with two vertex-disjoint facia…

Targeted Graham conjecture. Herscovici et al. conjectured that

Let $G$ and $H$ be graphs, let $G\mathbin{\square}H$ denote their Cartesian product, and let $\operatorname{gp}^-(G)$ denote the lower general position number of $G$. Kruft's conje…

Let $G$ be a graph. A set $S\subseteq V(G)$ is a terminal set if $S$ is a general position set of $G$ and adding any vertex $u\in V(G)-S$ to $S$ creates three-in-a-line with $u$ as…

Wang–Wu's path-product conjecture.

Wang–Wu's conjecture.

Lower-bound accuracy conjecture. The lower bounds differ from the exact values by at most a constant depending on $m$ and independent of $n$.

Let $G$ and $H$ be non-trivial graphs, and suppose that their Cartesian product $G\square H$ is planar. Planar Cartesian product conjecture. The graph $G\square H$ is interval colo…

2-domination conjecture for cylinders. The authors conjecture that

Roman domination lower-bound conjecture. Assuming that the observed pattern remains the same for larger values of $m$,

A path factor of a graph is a factor whose components are paths on at least two vertices. Let $P_m$ be the path on $m$ vertices, and let $\Delta(G)$ denote the maximum degree of a…

A path factor of a graph is a factor whose components are paths on at least two vertices. For a graph $G$, let $Delta(G)$ denote its maximum degree, and let $P_n$ be the path on…

Let $G$ be a connected graph. The resistance distance $R_G[u,v]$ between vertices $u$ and $v$ is the net effective resistance between them when each edge of $G$ is replaced by a un…