Partition Types

For a graph \( G \) having chromatic number \( k \), an equivalence relation is defined on the set \( X \) consisting of all proper vertex \( k \)-colorings of \( G \). This leads naturally to an equivalence relation on the set \( \mathcal{P} \) consisting of all partitions of \( V(G) \) into \( k \) independent subsets of color classes. The notion of a partition type arises and the algebra of types is investigated.