## 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

1more comments