Skip to main content
added 44 characters in body
Source Link

Since there is no mention of it, I will make one.

The direct product of graphs $G$ and $H$ is defined like this: $V(G \times H) = V(G) \times V(H)$ and $E(G\times H)$ contains only $((g_1, h_1),(g_2, h_2))$ such that $(g_1, g_2) \in E(G)$ and $(h_1, h_2) \in E(H)$.

In your properly edge colored graphs, if one considers all the pairs of monochromatic subgraphs (i.e., maximal subgraphs all of whose edges are the same color)---one in $G$ and the other in $H$---and takes their direct product, then one gets the same result as your product.

The direct product is well-studied---see the book by Imrich and Klavzar. There are also other products such as the normal (strong) product, lex product, cartesian product, etc. that might also be of interest.

Since there is no mention of it, I will make one.

The direct product of graphs $G$ and $H$ is defined like this: $V(G \times H) = V(G) \times V(H)$ and $E(G\times H)$ contains only $((g_1, h_1),(g_2, h_2))$ such that $(g_1, g_2) \in E(G)$ and $(h_1, h_2) \in E(H)$.

In your properly edge colored graphs, if one considers pairs of monochromatic subgraphs (i.e., maximal subgraphs all of whose edges are the same color) and takes their direct product, then one gets the same result as your product.

The direct product is well-studied---see the book by Imrich and Klavzar. There are also other products such as the normal (strong) product, lex product, cartesian product, etc. that might also be of interest.

Since there is no mention of it, I will make one.

The direct product of graphs $G$ and $H$ is defined like this: $V(G \times H) = V(G) \times V(H)$ and $E(G\times H)$ contains only $((g_1, h_1),(g_2, h_2))$ such that $(g_1, g_2) \in E(G)$ and $(h_1, h_2) \in E(H)$.

In your properly edge colored graphs, if one considers all the pairs of monochromatic subgraphs (i.e., maximal subgraphs all of whose edges are the same color)---one in $G$ and the other in $H$---and takes their direct product, then one gets the same result as your product.

The direct product is well-studied---see the book by Imrich and Klavzar. There are also other products such as the normal (strong) product, lex product, cartesian product, etc. that might also be of interest.

Source Link

Since there is no mention of it, I will make one.

The direct product of graphs $G$ and $H$ is defined like this: $V(G \times H) = V(G) \times V(H)$ and $E(G\times H)$ contains only $((g_1, h_1),(g_2, h_2))$ such that $(g_1, g_2) \in E(G)$ and $(h_1, h_2) \in E(H)$.

In your properly edge colored graphs, if one considers pairs of monochromatic subgraphs (i.e., maximal subgraphs all of whose edges are the same color) and takes their direct product, then one gets the same result as your product.

The direct product is well-studied---see the book by Imrich and Klavzar. There are also other products such as the normal (strong) product, lex product, cartesian product, etc. that might also be of interest.