Skip to main content
3 of 4
added 111 characters in body

Does a critical graph have to be product-irreducible?

A finite, simple, undirected graph $G=(V,E)$ is said to be (vertex-)critical if for all $v\in V$ we have $\chi(G\setminus\{v\}) < \chi(G)$. (In this context, $\chi(\cdot)$ denotes the chromatic number.)

Is there a vertex-critical graph $G = (V,E)$ with $|V|> 1$ and $G \cong H_1\times H_2$ for some graphs $H_1, H_2$? (Here, $H_1 \times H_2$ denotes the categorical, or tensor, product of graphs.)