98 problems

Symmetry characterization. $I(G\circ H;x)$ is symmetric for every graph $G$ if and only if $H=K_r-e$ for some $r\geq 2$.

Let $\mathsf{T}$ be the tree in Fig., and let $T$ be any nontrivial tree with root $r$. Define $G_1=T(r) \odot \mathsf{T}(4)$ and $G_2=T(r) \odot \mathsf{T}(7)$. Smith normal form…

Let $K_{n,m}$ be the complete bipartite graph with parts of sizes $n$ and $m$, and let $K_2$ be the complete graph on two vertices. Write $Z_q(G)$ for the $q$-analogue of the zero…

For each integer $k\geq2$, consider the Cartesian product $C_{2k}\square P_2$ of the cycle $C_{2k}$ and the path $P_2$. The notation $\operatorname{ex}(n,H)$ denotes the maximum nu…

Let $G$ and $H$ be graphs. Their strong product $G\boxtimes H$ has vertex set $V(G)\times V(H)$, with two vertices $(g_1,h_1)$ and $(g_2,h_2)$ adjacent when either $g_1=g_2$ and…

Hedetniemi's conjecture.

Let $G_1$ and $G_2$ be graphs, let $p_1,p_2$ be positive integers, and let $f_{(p_1,p_2)}$ denote the corresponding generalized pebbling number, with $f_{p_i}(G_i)$ the one-factor…

Let $H$ be a finite graph, and write $f_H(r)$ for its growth function, namely the maximum number of vertices in a ball of radius $r$. For graphs $G_1,\dots,G_k$, let…

Let $C_r$ denote the cycle on $r$ vertices. Lu et al.'s conjecture. For positive integers $m,n$, … The supplied text establishes the corresponding values for products involving eve…

Let $G_1$ and $G_2$ be graphs, and let $\Delta$ be a common upper bound for their maximum degrees, so that $\Delta(G_1)\leq\Delta$ and $\Delta(G_2)\leq\Delta$. Borowiecki–Jozef's a…

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

Havet–Horsch–Rambaud's lexicographic-product conjecture. For every graph $G$ and every positive integer $t$,

Let $(\Gamma,\Sigma)$ be a nontrivial graph pair, meaning that $\Gamma$ and $\Sigma$ are coprime connected twin-free graphs and exactly one of them is bipartite. Assume that the gr…

Coarse separability conjecture. The graph $G$ has a disconnecting clique if and only if the graph product $\Gamma(G)$ is coarsely separable by a family of subexponential growth.

Balanced complete-bipartite Cartesian-product conjecture. If any precoloring of at most $k < r$ edges of $G$ can be extended to a proper $\chi'(G)$-edge-coloring of $G$, then any p…

General Cartesian-product conjecture. Every precoloring of at most $k+l+1$ edges of $G \square H$ is extendable to a proper $(\chi'(G)+\chi'(H))$-edge-coloring of $G \square H$.

Casselgren, Petros and Fufa's conjecture. If every precoloring of at most $k < \chi'(G)$ edges of $G$ can be extended to a proper $\chi'(G)$-edge-coloring, then every precoloring o…

The graph-product conjecture. The free product $\ast_{v\in V}\Gamma_v$ is weakly sofic, and, more generally, $G_X$ is weakly sofic for every graph $X=(V,E)$ on $V$.

The graph-product conjecture. The free product $\ast_{v\in V}\Gamma_v$ is $\mathbb{K}$-linear sofic, and, more generally, $G_X$ is $\mathbb{K}$-linear sofic for every graph…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, let $\alpha(G)$ be the independence number, let $\chi_f(G)$ be the fractional chromatic number, and let $\Box$ denote the Carte…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, let $\chi_f(G)$ denote the fractional chromatic number of a graph $G$, and let $W_{2t+1}^{\Box 2}$ be the Cartesian square of t…

Let $W_5$ be the join of the cycle $C_5$ with $K_1$, let $\alpha(G)$ denote the independence number of $G$, and let $W_5^{\Box 4}$ be the fourth Cartesian power of $W_5$. Fourth-po…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, let $\alpha(G)$ be the independence number of $G$, and let $G\Box H$ denote the Cartesian product of graphs. For $t\geq 2$, con…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, and let $d4b0(G)$ denote the ultimate independence ratio of a graph $G$. For odd wheels, $d4b0(W_{2t+1})$ is bounded below by…

Let $G$ and $H$ be graphs, let $k\text{?}$ be a positive integer, and write $\varphi$ for the $b$-chromatic number and $G^k$ for the $k$-th graph power. Cartesian-product power con…