Partition Types

Abstract

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.