On 3-Chromatic Distance-Regular Graphs

A. Blokhuis, A.E. Brouwer, W.H. Haemers

Research output: Working paperDiscussion paperOther research output

248 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages15
Volume2006-120
Publication statusPublished - 2006

Publication series

NameCentER Discussion Paper
Volume2006-120

Keywords

  • distance-regular graphs
  • chromatic number

Fingerprint Dive into the research topics of 'On 3-Chromatic Distance-Regular Graphs'. Together they form a unique fingerprint.

  • Cite this

    Blokhuis, A., Brouwer, A. E., & Haemers, W. H. (2006). On 3-Chromatic Distance-Regular Graphs. (CentER Discussion Paper; Vol. 2006-120). Operations research.