4
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I think you should specify what product on graphs you are considering here (e.g. en.wikipedia.org/wiki/Cartesian_product_of_graphs or en.wikipedia.org/wiki/Tensor_product_of_graphs or en.wikipedia.org/wiki/Strong_product_of_graphs). Also clearly you mean to assume $H_1$ and $H_2$ have more than one vertex. $\endgroup$
    – Sam Hopkins
    Commented Nov 1, 2023 at 19:07
  • $\begingroup$ Thanks - I was thinking of the categorical product of graphs and will put this in the question. Apologies for the ambiguity. $\endgroup$
    – Dominic van der Zypen
    Commented Nov 2, 2023 at 8:14
  • 1
    $\begingroup$ @SamHopkins Actually, in the context of the tensor product, you don't need to explicitly exclude the one point graph $G_1$, because $G\times G_1$ is always a graph with no edges (all points are isolated), and vertex-critical graphs are always connected $\endgroup$
    – Dominic van der Zypen
    Commented Nov 2, 2023 at 8:19
  • $\begingroup$ $G\setminus\{v\}$ means removing all adjacent edges as well. If so, since the Euler-characteristic of a graph is the number of vertices minus the number of edges, vertex-cricical just means that at every vertex there are at least to edges. Thus for example $C_3\times C_2 \cong C_6$ is an example. $\endgroup$
    – HenrikRüping
    Commented Nov 2, 2023 at 8:35
  • 3
    $\begingroup$ @HenrikRüping I believe $\chi(G)$ here denotes the chromatic number rather than the Euler characteristic. $\endgroup$
    – Emil Jeřábek
    Commented Nov 2, 2023 at 9:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .