<p>Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (<a href="https://doi.org/10.1007/BF01305232" rel="nofollow noreferrer">Cai-Furer-Immerman</a>). 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.</p>

CC BY-SA 3.0
2017-09-10T01:39:00.573Z
How about degree $\leq 3$ and bipartite?
Turbo
CC BY-SA 3.0
2017-09-10T18:51:37.953Z
@777: that's equivalent to general degree $\leq 3$, up to a quadratic term. Just add a new vertex on every edge.
Joshua Grochow
CC BY-SA 3.0
2017-09-11T08:12:20.347Z
$k$-WL fails on iso-regular graphs, where $k$ is constant and there are at most degree three iso-regular graphs.
new
CC BY-SA 3.0
2017-09-12T02:17:22.350Z
@shivd what does "iso-regular" mean?
Joshua Grochow
CC BY-SA 3.0
2017-09-12T11:40:09.363Z
@ Joshua Grochow  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).
new
CC BY-SA 3.0
2017-09-12T15:33:44.110Z
@shivd: I don't yet see why k-WL should fail on k-isoregular graphs. As I understand it now (e.g. [here](https://arxiv.org/pdf/1404.7716.pdf)), k-isoregular means that for every $X \subseteq V$ with $|X| \leq k$, the number of vertices $v$ that are adjacent to *every* element of $X$ only depends on the isomorphism type of the subgraph induced by $X$. But k-WL also detects information about # of vertices adjacent to subsets of $X$ rather than all of $X$... Also, this result you mention sounds very interesting; can you point me to a reference for existence of degree 3 k-isoregular graphs?
Joshua Grochow
CC BY-SA 3.0
2017-09-12T16:14:01.893Z
@Joshua Grochow See page no -5, second paragraph in the link https://arxiv.org/pdf/1101.5211.pdf
new
CC BY-SA 3.0
2017-09-12T16:34:54.270Z
@shivd: Ah, right, sorry, I was being silly - my previous issue is handled because it's not just for all vertex sets of size *exactly* k, but for all vertex sets of size $\leq k$. However, the issue w/ k-isoregular is that 5-isoregular implies that a graph is one of a short list [Cameron](https://doi.org/10.1016/0095-8956(80)90063-5), and those can easily be tested for iso using a "combinatorial" algorithm (that is, without the group-theoretic machinery of Babai, Luks), even though k-WL doesn't work. (Similar to how k-WL doesn't work for complete graphs, but testing iso to them is still easy.)
Joshua Grochow
CC BY-SA 3.0
2018-02-05T11:56:48.660Z
@ Joshua Grochow Is degree reduction trick going to work here? There exists a reduction that, given two graphs of size n and of maxi- mal degree at most d, produces two graphs of maximal degree at most ⌈d/2⌉. These graphs are isomorphic if and only if the original graphs are. Now in my case degree of resultant graphs is going to be at most 2. which I can do in combinatorial way.
new
CC BY-SA 4.0
2018-08-14T13:00:47.477Z
@new: what is this reduction, and what does it do to the size of the graph?
Joshua Grochow
CC BY-SA 3.0
2017-09-09T20:16:44.080Z
2017-09-10T20:18:20.387Z
2017-09-10T20:18:20.387Z
Joshua Grochow
<p>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. </p>

<blockquote>
  <p><strong>Question</strong> : 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?</p>
</blockquote>

<p>I thought of using Weisfeiler-Lehman procedure, but it fails on regular graphs.</p>

<p>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. </p>

<p>$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).</p>

CC BY-SA 3.0
2017-09-12T16:21:21.230Z
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](https://arxiv.org/abs/1307.2187). 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...
Joshua Grochow
CC BY-SA 3.0
2017-09-12T17:10:00.690Z
Also, the thing to really try is WL together with individualizing a small number of vertices.
Joshua Grochow
CC BY-SA 3.0
2017-09-20T12:34:38.737Z
I think it is possible to come-up with an $O(\sqrt n \log n)$ individualisation set size, see this https://people.cs.uchicago.edu/~laci/papers/13focs-SRG.pdf, but smaller size seems difficult.
new
<graph-isomorphism>
A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)
new
# A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

(Asked by: username_0 on 2017-09-09)

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

**Tags:** graph-isomorphism
> **Comments:**
> **username_1**: 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](https://arxiv.org/abs/1307.2187). 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...  
> **username_1**: Also, the thing to really try is WL together with individualizing a small number of vertices.  
> **username_0**: I think it is possible to come-up with an $O(\sqrt n \log n)$ individualisation set size, see this https://people.cs.uchicago.edu/~laci/papers/13focs-SRG.pdf, but smaller size seems difficult.  

---

## 1 answers

### Answer by username_1 on 2017-09-09. Score: 5 | Accepted answer

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 ([Cai-Furer-Immerman](https://doi.org/10.1007/BF01305232)). 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.

> **Comments:**
> **username_2**: How about degree $\leq 3$ and bipartite?  
> **username_1**: @777: that's equivalent to general degree $\leq 3$, up to a quadratic term. Just add a new vertex on every edge.  
> **username_0**: $k$-WL fails on iso-regular graphs, where $k$ is constant and there are at most degree three iso-regular graphs.  
> **username_1**: @shivd what does "iso-regular" mean?  
> **username_0**: @ Joshua Grochow  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).  
> **username_1**: @shivd: I don't yet see why k-WL should fail on k-isoregular graphs. As I understand it now (e.g. [here](https://arxiv.org/pdf/1404.7716.pdf)), k-isoregular means that for every $X \subseteq V$ with $|X| \leq k$, the number of vertices $v$ that are adjacent to *every* element of $X$ only depends on the isomorphism type of the subgraph induced by $X$. But k-WL also detects information about # of vertices adjacent to subsets of $X$ rather than all of $X$... Also, this result you mention sounds very interesting; can you point me to a reference for existence of degree 3 k-isoregular graphs?  
> **username_0**: @Joshua Grochow See page no -5, second paragraph in the link https://arxiv.org/pdf/1101.5211.pdf  
> **username_1**: @shivd: Ah, right, sorry, I was being silly - my previous issue is handled because it's not just for all vertex sets of size *exactly* k, but for all vertex sets of size $\leq k$. However, the issue w/ k-isoregular is that 5-isoregular implies that a graph is one of a short list [Cameron](https://doi.org/10.1016/0095-8956(80)90063-5), and those can easily be tested for iso using a "combinatorial" algorithm (that is, without the group-theoretic machinery of Babai, Luks), even though k-WL doesn't work. (Similar to how k-WL doesn't work for complete graphs, but testing iso to them is still easy.)  
> **username_0**: @ Joshua Grochow Is degree reduction trick going to work here? There exists a reduction that, given two graphs of size n and of maxi- mal degree at most d, produces two graphs of maximal degree at most ⌈d/2⌉. These graphs are isomorphic if and only if the original graphs are. Now in my case degree of resultant graphs is going to be at most 2. which I can do in combinatorial way.  
> **username_1**: @new: what is this reduction, and what does it do to the size of the graph?  

---

