It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC.
I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by Johannes Köbler (see this)
My question : Luks has given an algorithm for trivalent GI (degree at most three ) (see section 2). Is that algorithm also not parallelizable ? If yes provide the reference.
