Background/Motivation
---------------------


I'm working on algorithms for canonical labeling of a certain class of graphs (motivated by biology). The "difficult" instances of this problem can be reduced to graphs of the type mentioned in the title. 


*Rigid* refers to graphs having only the trivial automorphism, i.e. no symmetry.


*Chromatic index* refers to the smallest number of colors needed for an edge coloring of the graph, i.e. a coloring such that no node is incident to two edges of the same color.


So, all nodes in these graphs have the same "local view", i.e. exactly one incident edge for each of the N distinct colors.


I'm interested in undirected graphs in the first instance, but ultimately also in directed graphs; in the latter case, I allow the same color be used for two edges incident to a given node if one is outgoing and the other is incoming. 


**Edit:** To motivate the chromatic index property, I am in fact working with graphs which have colors assigned to edges, and these happen to constitute edge colorings. So I get edge colorings for free - I'm not computing them.


**Edit:** An outline of the canonical labeling algorithm we are looking at, in case that is relevant or of interest. Edges are colored, and isomorphism must preserve edge colors. We assume a total ordering of colors. This ordering then induces a total ordering on nodes, based on e.g. depth first searches which follow edges according to the color ordering. The fact that each node has at most one edge of a given color means that a node uniquely determines a depth first search from that node. One can then pick a "least" node, and construct a canonical labeling based on a search from that node. If there are "many" automorphisms, one can quickly reduce the number of nodes under consideration. The problem arises when there are "few" automorphisms - e.g. just the trivial one - which was the original motivation for this question.


The question
------------


I'm trying to better understand this class of connected, rigid, N-regular graphs with chromatic index N. Specifically:


1) Are there any well-known or extensively studied examples of such graphs?


2) Are there any established results relating to such graphs, e.g. on existence?


3) Are there existing results on the complexity of isomorphism or canonical labeling for this class of graphs?


I'm not very hopeful, since I have done my best to search the literature. But I'm not an expert in graph theory, and I'd be grateful for any pointers.


Many thanks,
Michael



Isomorphism of connected, rigid, N-regular graphs with chromatic index N?
Based on the further information, I am addressing the question of canonical labelling of connected, edge-coloured, regular graphs. I don't recall any literature on this. Let $n$ be the number of vertices and $d$ the degree.


As you noted, DFS (or BFS, etc) can be used to make a unique labelling for each starting vertex. Then you can choose a "best" starting vertex according to some ordering on labelled graphs. This gives an $O(n^2d)$ canonical labelling algorithm. In practice you can do two things to make it faster.


(1) Compute some invariant of the vertices and only consider starting vertices that that have the rarest value of the invariant. Think of the number of triangles at a vertex, the number of vertices at distance two from a vertex, etc. Probably in your case some use of colours is best. The length of the cycles formed by two colours might be useful. You need to experiment to find the most efficient invariant for your application.


(2) Don't compute complete labellings before comparing them. Keep the best labelling seen so far and compare other labelings to it as they are being computed. Most labellings will be aborted early.


I don't see a fundamental reason why O(nd) is impossible, but I don't see an algorithm achieving that either. Knowing in advance that the automorphism group is trivial will not help. 


Regarding the existence problem, the complete graph on an even number of vertices can be properly edge coloured (look up perfect factorizations, also called 1-factorization, of complete graphs). Just take the edges with some set of colours to get examples of any plausible degree. (However, this does not get all possible examples.)


