Alladi Ramakrishnan Hall

Color refinement and an LP based approach to Graph Isomorphism

Gaurav Rattan

IMSc

Color refinement is a classical efficient procedure for showing that two given graphs are non-isomorphic. However, it does not succeed on all graphs. We call a graph amenable to color refinement if it succeeds in distinguishing it from any nonisomorphic graph. We
characterize amenable graphs and give an $O((n+m)\log n)$ time algorithm for testing amenability, where $n$ and $m$ denote the number of vertices and the number of edges in the input graph.

A graph is called compact if the polytope of its fractional
automorphisms is integral. Tinhofer noted that isomorphism testing for compact graphs is in polynomial time by linear
programming, but no efficient algorithm for recognizing compact graphs is known. We show that amenable graphs are
compact. We show, among other results, that amenability is P-complete and compactness is \textsc{P}-hard.