Canonical way of coloring graphs (individualization) for isomorphism purpose

Question

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:

1. How exactly is this coloring done?
2. What exactly is a canonical coloring?

Answer 1

1. Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ to those of the same color $c$ in $H$). You pick a vertex $v$ in $G$ and assign it a new color, say $c$, that has not been used before. This is called "individualization." Then for each vertex $w \in V(H)$ you will, in turn, try coloring $w$ with $c$ and see if there is an isomorphism $G \to H$ that respects this new coloring. (This incurs a multiplicative cost of $|V(H)|$, so you don't want to do this too often.) In other words, you are guessing the vertex $v$, and then trying to see which vertices of $H$ it can possibly map to.

To aid in this quest, frequently individualization is followed by a process called (Weisfeiler-Lehman) refinement. What happens here is that you assign new colors to each vertex according to the multi-set of colors of its neighbors. Then you do this again. Then you do this again. And you keep doing this until the partition of vertices by color does not change.

2. An isomorphism-invariant coloring of graphs is a method of assigning colors to vertices so that if two graphs are isomorphic, then there is an isomorphism between them that sends vertices of color $c$ to vertices of color $c$. Some authors will call this coloring canonical - and indeed, in the paper you cite, it may be that all they need is a canonical coloring in which each color class has bounded size. (Other authors might say that a canonical coloring is an isomorphism-invariant coloring in which each vertex receives a color that is distinct from that of all other vertices. In this way, if we can compute a canonical coloring of two graphs $G,H$, then there is only one possible isomorphism between them (namely, the one that respects the colors), and it is easy to check whether this is actually an isomorphism.)

Combined with individualization, one can talk about a coloring that is canonical relative to the individualizations that have been made previously. That is, it may not be canonical with respect to isomorphisms of the original graphs, but given the vertices that have been colored so far it is canonical. (In this sense individualization is a form of "partial brute-force search," in which you keep track of how the guesses you've made so far constrain your future search.)