In a paper I am working on, I come across a term called "graph canonisation "

According to math-world Wolfram:

A canonical labeling, also called a canonical form, of a graph $G$ is a graph $G^{'}$ which is isomorphic to $G$ and which represents the whole isomorphism class of $G$ (Piperno 2011). The complexity class of canonical labeling is not known

Could one elaborate on that ?

Motivation : I am working on graph isomorphism (See this paper by E.M Luks).

  • 1
    $\begingroup$ Very relevant is (Greg Kuperberg's answer in) this thread. Also note the Borel-reducability results of Friedman and Stanley. $\endgroup$ – Peter Heinig Aug 26 '17 at 10:08

The wikipedia article seems to explain it pretty well: https://en.wikipedia.org/wiki/Graph_canonization

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.