Testing isomorphism of circular-arc graphs in polynomial time
classification
💻 cs.DS
math.CO
keywords
circular-arcverticesarcsgraphsisomorphismadjacentalgorithmassociated
read the original abstract
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.