We give some necessary conditions for a graph to be 3-chromatic in terms of the spectrum of the adjacency matrix.For all known distance-regular graphs it is determined whether they are 3-chromatic.A start is made with the classification of 3-chromatic distance-regular graphs, and it is shown that such graphs, if not complete 3-partite, must have ..<1.
|Place of Publication||Tilburg|
|Number of pages||15|
|Publication status||Published - 2006|
|Name||CentER Discussion Paper|
- distance-regular graphs
- chromatic number