On 3-chromatic distance-regular graphs

被引：0
作者：
Aart Blokhuis
Andries E. Brouwer
Willem H. Haemers
机构：
[1] Technological University Eindhoven,Department of Mathematics
[2] Tilburg University,Department of Econometrics & O.R.
来源：
Designs, Codes and Cryptography | 2007年 / 44卷
关键词：
Distance-regular graphs; Chromatic number; 05E30; 05C15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：293 / 305
页数：12
相关论文
共 21 条
  • [1] Brouwer AE(1982)The uniqueness of the near hexagon on 729 points Combinatorica 2 333-340
  • [2] Brouwer AE(1983)The structure of near polygons with quads Geom Dedicata 14 145-176
  • [3] Wilbrink HA(1994)Near polygons and Fischer spaces Geom Dedicata 49 349-368
  • [4] Brouwer AE(2005)A computer-assisted proof of the uniqueness of the Perkel graph Des Codes Cryptogr 34 155-171
  • [5] Cohen AM(1985)The chromatic number of the product of two 4-chromatic graphs is 4 Combinatorica 5 121-126
  • [6] Hall JI(2006)5-chromatic strongly regular graphs Discrete Math 306 3083-3096
  • [7] Wilbrink HA(1993)There exists no distance-regular graph with intersection array (5,4,3;1,1,2) Eur J Combin 14 409-412
  • [8] Coolsaet K(1976)Some NP-complete graph problems Theor Comput Sci 1 237-267
  • [9] Degraer J(1990)The Eur. J Combin 11 373-379
  • [10] El Zahar M(1992)-geometry for Discrete Math 103 271-277
123