The walk partition and colorations of a graph

We study the partitions of a graph G with vertices labeled 1,2,…,n. A matrix notation for partitions is devised which reflects a partial order among partitions and provides a matrix characterization (in terms of the adjacency matrix A of G) of a coloration or equitable partition. An especially useful partition is one based on the number of walks issuing from each vertex. This is not generally a coloration (sufficient conditions are given) but nevertheless plays a special role relative to colorations. The spectrum of G, Sp(G), has a “main part”, the set of eigenvalues with an eigenvector not orthogonal to e (the column of 1s). We disprove a conjecture of Harary and Schwenk about the main part of the spectrum and prove an alternate characterization. The walk partition appears here and also in a relation between the main parts of the spectra of G and ?, its complement.