Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism is solvable in polynomial time (Theorem 4, page 8).
I have a problem understanding the outline of the proof for Theorem 4 and therefore the proofs of the different cases itself. The main idea is to construct colored graphs of bounded color valence for which the problem is solvable in polynomial time according to Theorem 5.
For creating such graphs one tries to find a canonical coloring. One such method is called individualization.
As this method is just described as:
We guess an ordered set of vertices of constant size, color the vertices in this set with singleton colors, and then color the remaining vertices according to their adjacencies to the vertices in the ordered set.
and not further specified in the following proofs.
I have two questions:
- How exactly is this coloring done?
- What exactly is a canonical coloring?