Let $n\geq 2$ be a positive integer. For the purposes of this definition, let a colored graph be a finite undirected graph in which each edge is colored with one of $n$ colors so that no vertex is incident with two edges of the same color. (Without loss of generality, we suppose that every vertex is incident with exactly one edge of each color; add loops wherever necessary.) If $G_1$ and $G_2$ are two colored graphs, we define a product $H=G_1\times G_2$ as follows.
- The vertices of $H$ are the ordered pairs of vertices $(v_1,v_2)$, where $v_i$ is a vertex of $G_i$.
- If $(v_1,w_1)$ and $(v_2,w_2)$ are edges of the same color in $G_1$ and $G_2$, respectively, then there is an edge (also of the same color) between $(v_1,v_2)$ and $(w_1,w_2)$ in $H$.
Examples. Consider $n=3$, the simplest interesting case (and the one that interests me most). Let $K'_3$ be the complete graph on three vertices with an extra loop at each vertex, and let $K_4$ be the complete graph on four vertices. (There is essentially only one way to to color each of these graphs.)
- $K'_3\times K'_3$ has two components: one is a copy of $K'_3$ and the other has six vertices.
- $K'_3\times K_4$ is a connected graph with twelve vertices.
- $K_4\times K_4$ has four components, each of which is a copy of $K_4$.
Does this have a name? Has it been studied? It seems plausible enough to me that this may be a well-studied thing. At the moment, I'm especially interested in necessary/sufficient criteria for the product of connected colored graphs to be connected, or more generally an efficient way to count (or at least estimate) the number of components of the product, but any information that exists is reasonably likely to be useful to me.
My motivation here comes from some problems I'm working on in combinatorial number theory. I have various (colored) graphs that I associate to a positive integer $N$, and in many cases the graph corresponding to $MN$ is the product in this sense of the graphs corresponding to $M$ and $N$ whenever $\gcd(M,N)=1$. The graphs at prime powers are much simpler than the general case.