# A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

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).

• If you're going to try to avoid bounded tree-width, you might also try avoiding other FPT algorithms: bounded clique-width, bounded genus (or more generally bounded topological Hadwiger number), bounded eigenvalue multiplicity; see, e.g. Marx-Pilipczuk. Finding degree 3 graphs w/ all of these parameters unbounded could be hard; on the other hand, maybe having so many constraints will point you towards a construction... Sep 12 '17 at 16:21
• Also, the thing to really try is WL together with individualizing a small number of vertices. Sep 12 '17 at 17:10
• I think it is possible to come-up with an $O(\sqrt n \log n)$ individualisation set size, see this people.cs.uchicago.edu/~laci/papers/13focs-SRG.pdf, but smaller size seems difficult.
– new
Sep 20 '17 at 12:34

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know of a result ruling this out either. Aside from Babai's general algorithm (which is quasi-polynomial, not polynomial), I do not know another algorithm for degree 3 other than the one you mention.

• How about degree $\leq 3$ and bipartite?
– Mr.
Sep 10 '17 at 1:39
• @777: that's equivalent to general degree $\leq 3$, up to a quadratic term. Just add a new vertex on every edge. Sep 10 '17 at 18:51
• $k$-WL fails on iso-regular graphs, where $k$ is constant and there are at most degree three iso-regular graphs.
– new
Sep 11 '17 at 8:12
• @shivd what does "iso-regular" mean? Sep 12 '17 at 2:17
• @Joshua Grochow See page no -5, second paragraph in the link arxiv.org/pdf/1101.5211.pdf
– new
Sep 12 '17 at 16:14