I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent graph isomorphism, which is algebraic in nature.
Question : Is there a known graph isomorphism algorithm for graphs of degree at most three other than E.M Luks algorithm? Is there exist a combinatorial algorithm for trivalent graph isomorphism?
I thought of using Weisfeiler-Lehman procedure, but it fails on regular graphs.
Edit : I will use $k$-Weisfeiler-Lehman procedure; it is going to fail on the very small class of graphs called iso-regular graphs, Now I will divide this class into two classes;bounded tree width and unbounded tree width. For bounded tree width we already have a polynomial time (FPT algorithm) algorithm, unbounded tree-width class can be further divided into two subclasses; planar and non-planar, for planar, we already have a combinatorial algorithm that runs in $O(n^2)$ time, Now we are left with non-planar unbounded tree width iso-regular graphs. One thing is that I am not able to come up with an example of a graph, which is a non-planar unbounded tree width iso-regular graph of degree at most three.
$k$-iso-rgular graphs or $k$-tuple regular graphs : Graphs in which the number of common neighbours of any k-tuple of a given isomorphism type is constant (for instance, strongly regular graphs are 2-isoregular).