Return to Question

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

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

Let me add that in this context, $\chi(\cdot)$ denotes the chromatic number, and by $G\setminus\{v\}$ we mean the graph $\big(V\setminus\{v\}, E\cap [V\setminus\{v\}]^2\big)$, where $[X]^2 :=\big\{\{x,y\}:x\neq y \in X\big\}$ for any set $X$.

Question. 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.)

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

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

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

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

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

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

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