Graph Isomorphism Problem - Solved Special Cases

Solved Special Cases

A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:

• Trees
• Planar graphs (In fact, planar graph isomorphism is in log space, a class contained in P.)
• Interval graphs
• Permutation graphs
• Partial k-trees
• Bounded-parameter graphs
  • Graphs of bounded genus (Note: planar graphs are graphs of genus 0)
  • Graphs of bounded degree
  • Graphs with bounded eigenvalue multiplicity
  • k-Contractible graphs (a generalization of bounded degree and bounded genus)
  • Color-preserving isomorphism of colored graphs with bounded color multiplicity (i.e., at most k vertices have the same color for a fixed k) is in class NC, which is a subclass of P.