New answers tagged

0

Isomorphism of such graphs can be decided in polynomial time using $k$-Weisfeiler-Lehman method. Begin by partitioning the vertex set of a graph (or equivalently colouring the vertices) according to vertex valency. Then at each subsequent step the colour of each vertex is updated to reflect its previous colour together with the multiset of colours of its ...


5

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same ...


Top 50 recent answers are included