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.
Best Answer
If you wanted this for directed graphs, I would say this:
As Andy Putman suggests, look at Stallings Inventiones paper "The topology of finite graphs."
A directed graph colored with $n$ colors admits an obvious map to a colored oriented wedge of $n$ circles, $X$ say.
Given two directed colored graphs, the fiber product of the two maps to $X$ may be defined the same way you are defining your product, but where the condition being that there is an edge going from $(a,b)$ to $(c,d)$ colored $m$ if there is an edge from $a$ to $c$ colored $m$ and an edge from $b$ to $d$ colored $m$ (so the orientation is taken into account).
This graph is smaller than yours, but has the advantage of being the pullback of a simple diagram.
I think that you should be able to take care of the undirected case by thinking of each edge of your graph as two edges, one for each orientation, or some such device. There's a nice way to think about this in Gersten's paper "Intersection of finitely generated subgroups of free groups and resolutions of graphs" in the same issue of Inventiones---he talks about "ghost edges."