# Canonical way of coloring graphs (individualization) for isomorphism purpose

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?

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.
1. 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.)
• To create a colored graph of bounded color valence, what we try to achieve: Create a colored graph (that respects isomorphism and doesn't have to be proper) by e.g. like in case 1 individualizing a vertex and showing that its co-degree/degree is bounded (while bounded means that one can't create vertices with arbitrarly large degree/co-degree, even when $V(G)=n\to\infty$). Given these properties one can create a colored graph with bounded color valence by assigning the same color to all neighbors/non-neighbors of the one individualized vertex. Is that the right approach to the problem? Jan 14, 2016 at 15:59