137 problems

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$.

Let $T_1$ and $T_2$ be trees of order at least $2$, and let $\gamma_{\mathrm{pr}}(T)$ denote the paired domination number of a graph $T$. Strict paired domination conjecture. … The…

Let $G$ and $G'$ be graphs, and let $\mathcal{S}$ and $\mathcal{S}'$ be sets of distributions on $G$ and $G'$, respectively. The Cartesian product $G\Box G'$ is the graph product d…

Let $G$ and $H$ be graphs, and let $\operatorname{im}(G)=t$ and $\operatorname{im}(H)=r$, where $\operatorname{im}$ denotes the immersion number. Let $G\boxtimes H$ be their strong…

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.

Let $G$ and $H$ be graphs, and let $g$ and $h$ be maximum fractional cliques of $G$ and $H$, respectively. A fractional clique is a map $f:V(G)\to[0,1]$ whose sum on every independ…

Let $G$ and $H$ be graphs, let $G\times H$ denote their direct product, and write $i(G)$ for the independent domination number of $G$. Nowakowski–Rall's conjecture. For all graphs…

Poljak–Rödl formulation. Hedetniemi's conjecture is equivalent to

For a positive integer $t$, let $K_t\square K_t\square K_t$ be the Cartesian product of three complete graphs on $t$ vertices. A graph is path-pairable if every pairing of its vert…

The fall chromatic number equality conjecture. The equality

For fixed $l$, let $\mathcal P_l^n$ denote the sequence of $n$-fold Cartesian powers of the path $P_l$. Let $\tau$ denote the pebbling threshold and $N$ the number of vertices in t…

Let $\mathcal G_{n,p}$ be the random graph model, with $p=p(n)$, and let $G,H$ be independent graphs sampled from $\mathcal G_{n,p}$. Let $G\mathbin{\square}H$ be their Cartesian p…

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 $T$ be a tree and $H$ be a graph. The cooling number $**CL**$ of a graph is denoted by $\operatorname{CL}$. Cooling-number conjecture. … This conjecture proposes an improvement…

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…

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…

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…