Let us consider a graph G = (V, E). A k-coloring (S,, . . . , Sk) of its nodes is called canonical if any node u E V of any color i is contained in a clique K of size i such that K n S' # ff for 1 CjGi.
A connected order on a connected graph G = (V, E) is any order u1 < a --c up such that {u l,"', Vi} induces a connected graph for any i 1~ i G 1 V I= p. We prove that any sequential node coloring based on any connected order gives a canonical coloring of any connected subgraph G' of G if and only if G is a parity graph without Fish (a Fish is a forbidden graph on 6 nodes).
Given an order of the nodes of a graph G, a sequential node coloring is an algorithm which scans the nodes in this order and gives to each one the smallest available color.
A connected order in a connected graph G is any order vu1 < l l l < vp such that 1 VI,..., Vi} induces a connected graph for any i 1s i < IV1 = p. For a non connected graph G it will simply be the concatenation of connected orders of the connected components of G.
Gi will denote the subgraph induced by {V 1, . . . vi}. The algorithm consisting of a Sequential node coloring based on any Connected ORdEr will be called SCORE. In other words, we choose at the beginning any node cf the graph. Then, at each step, we choose any node which is adjacent to at least one already colored node and give it the smallest available color. When there is no such node, we start with a 2ode in another connected component (provided all nodes are not colored yet).
Our purpose is to study a class of graphs for which SCORE always produces optimal colorings for the graph itself and for a collection of subgraphs. This class will be closely related to parity graphs. These were introduced by Olaru and Sachs [4] as graphs characterized by the following property: every odd cycle of length 3 5 has two crossing chords.
Later they were called purity graphs because they can also be characterized by the