3 revised wording

In a similar spirit to David Eppstein's answer, one can relate this construction to the tensor product (a.k.a. the Cartesian product) of graphs and digraphs. If it is a standard construction, I'm not aware of it.

We may represent edge-colourings of the sort you describe by introducing a new node for each edge-colour, subdividing each edge of the original graph, and linking the central vertex of each edge to the appropriate colour-node. (This requires a multi-graph construction if you have loops in the original graph; you could fix this with additional subdivisions if you prefer simple-ish graphs.) If you use directed arcs to the colour nodes, you could use the asymmetry to make this construction reversible, up to permutation of the colours. Let us call this an edge subdivision model of a proper edge-colouring.

The tensor product of graphs G and H is a graph T such that V(T) = V(G) × V(H), and edge-relations { (g1,h1)(g2, h2) } ∈ E(T) such that {g1g2} ∈ E(G) and {h1h2} ∈ E(H). For digraphs, replace unordered pairs with ordered pairs. In terms of relations on the sets V(G) and V(H), this is the logical conjunction. It is easy to see that in digraphs, only those vertex-pairs (g1,h1)(g2, h2) which have consistent arc directions for each co-ordinate in the digraphs G and H will have arcs in the tensor product.

The consistency of arc-directions in tensor products of digraphs is what David remarks on abovein his response: if each node has one inbound arc and one outbound arc, in both graphs, the tensor product will have the same property. But it may be difficult to obtain a well-defined mapping from edge-colours to arc directions, because edge-colours don't have any asymmetry in them. This motivates finding a different way of encoding structural information in an edge than asymmetry --- such as the subdivision models I describe above.

If you take the tensor product of two coloured-subdivision graphs as I describe above, you get a first approximation to (an edge-subdivision model of) the graph construction you describe. There are two defects: (a) it has too many colours, one colour (a,b) for each pair of colours in the original colouring; and (b) it has vertices (v,e) which correspond to a vertex v ∈ V(G) in one co-ordinate and a subdivided edge e ∈ E(H) in another co-ordinate. However, from this tensor product we may easily obtain an induced subgraph, which is an edge-subdivision model of the graph construction you consider.

1. Eliminating excess colours: the colour-pairs (a,b) will be adjacent to nodes corresponding to the edge-pairs (eG, eH) where eG  E(G) has colour a and eH  E(H) has colour b. You wish to have only consistent edge-colourings; to do this, simply remove the "mismatched colour" nodes (a,b) for a ≠ b, and any vertex adjacent to them which correspond to edges with mismatched colours. Any remaining node (c,c) for some colour c may be identified as the 'colour node' for c in a new edge-subdivision model for a graph.

2. Eliminating vertex/edge type-mismatched pairs: in an edge-subdivision model for your construction, we obviously would only want pairs (eGeH) for eG ∈ E(G) and eH ∈ E(H) or pairs (vGvH) for vG ∈ V(G) and vH ∈ V(H), and no mismatched-type vertices (v,e). Fortunately, the vertex-nodes in the subdivision models are not adjacent to any colour; and so neither are mismatched-type nodes in the tensor product. In fact, mimatched-type vertices are only adjacent to other mismatched-type vertices. So we may restrict to the connected component(s) of the product graph which contains the colour nodes.

So, your construction can be 'simulated' by taking an induced subgraph (in which a pre-determined vertex subset is to be removed) of a tensor product of 'uncoloured' graphs and digraphs. However, I haven't heard of this construction being used before.

2 elaborated response slightly

We may represent edge-colourings of the sort you describe by introducing a new node for each edge-colour, subdividing each edge of the original graph, and linking the central vertex of each edge to the appropriate colour-node. (This requires a multi-graph construction if you have loops in the original graph; you could fix this with additional subdivisions if you prefer simple-ish graphs.) If you use directed arcs to the colour nodes, you could use the asymmetry to make this construction reversible, up to permutation of the colours. Let us call this an edge subdivision model of a proper edge-colouring.

The tensor product of graphs G and H is a graph T such that V(T) = V(G) × V(H), and edge-relations { (g1,h1)(g2, h2) } ∈ E(T) such that {g1g2} ∈ E(G) and {h1h2} ∈ E(H). For digraphs, replace unordered pairs with ordered pairs. In terms of relations on the sets V(G) and V(H), this is the logical conjunction. It is easy to see that in digraphs, only those vertex-pairs (g1,h1)(g2, h2) which have consistent arc directions for each co-ordinate in the digraphs G and H will have arcs in the tensor product; this .

The consistency of arc-directions in tensor products of digraphs is reminiscent what David remarks on above: if each node has one inbound arc and one outbound arc, in both graphs, the tensor product will have the same property. But it may be difficult to obtain a well-defined mapping from edge-colours to arc directions, because edge-colours don't have any asymmetry in them. This motivates finding a different way of your colour criterionencoding structural information in an edge than asymmetry --- such as the subdivision models I describe above.

If you take the tensor product of two coloured-subdivision graphs as I describe above, you will get a first approximation to (an edge-subdivision model of) the graph with n2 colours rather than nconstruction you describe. There are two defects: (a) it has too many colours, one 'colour' colour (a,b)a,b) for each pair of the colours a or bin the original colouringschema; and (b) it has vertices (v,e) which correspond to a vertex v ∈ V(G) in one co-ordinate and a subdivided edge e ∈ E(H) in another co-ordinate. If you remove all However, from this tensor product we may easily obtain an induced subgraph, which is an edge-subdivision model of the graph construction you consider.

• Eliminating excess colours: the colour-pairs other than (c,c) for each a,b) will be adjacent to nodes corresponding to the edge-pairs (eG, eH) where eG  E(G) has colour a and eH  E(H) has colour b.You wish to have only consistent edge-colourings; to do this, you will get simply remove the coloured-subdivision graph "mismatched colour" nodes (a,b) for a ≠ b, and any vertex adjacent to them which correspond to edges with mismatched colours. Any remaining node (c,c) for some colour c may be identified as the 'colour node' for c in a new edge-subdivision model for a graph.

• Eliminating vertex/edge type-mismatched pairs: in an edge-subdivision model for your constructionyou describe, we obviously would only want pairs (eG, eH) for eG ∈ E(G) and eH ∈ E(H) or pairs (vG, vH) for vG ∈ V(G) and vH ∈ V(H), and no mismatched-type vertices (v,e).Fortunately, the vertex-nodes in the subdivision models are not adjacent to any colour; and so neither are mismatched-type nodes in the tensor product. In fact, mimatched-type vertices are only adjacent to other mismatched-type vertices. So we may restrict to the connected component(s) of the product graph which contains the colour nodes.

• So, your construction can be 'simulated' by taking an induced subgraph (in which a pre-determined vertex subset is to be removed) of a tensor product of 'uncoloured' graphs and diagraphsdigraphs. However, I haven't heard of this construction being used before.