×

On 3-chromatic distance-regular graphs. (English) Zbl 1123.05094

Summary: 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 \(\lambda \leq 1\).

MSC:

05E30 Association schemes, strongly regular graphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brouwer AE (1982). The uniqueness of the near hexagon on 729 points. Combinatorica 2: 333–340 · Zbl 0509.05028 · doi:10.1007/BF02579429
[2] Brouwer AE and Wilbrink HA (1983). The structure of near polygons with quads. Geom Dedicata 14: 145–176 · Zbl 0521.51013 · doi:10.1007/BF00181622
[3] Brouwer AE, Cohen AM and Neumaier A (1989). Distance-regular graphs. Springer-Verlag, Berlin, Heidelbeg, Newyork · Zbl 0747.05073
[4] Brouwer AE, Cohen AM, Hall JI and Wilbrink HA (1994). Near polygons and Fischer spaces. Geom Dedicata 49: 349–368 · Zbl 0801.51012 · doi:10.1007/BF01264034
[5] Coolsaet K and Degraer J (2005). A computer-assisted proof of the uniqueness of the Perkel graph. Des Codes Cryptogr 34: 155–171 · Zbl 1056.05149 · doi:10.1007/s10623-004-4852-9
[6] Cvetković DM, Doob M, Sachs H (1980) Spectra of graphs: theory and applications. Deutscher Verlag der Wissenschaften, Berlin; Academic Press, New York (Third edition, Johann Abrosius Barth Verlag, Heidelberg-Leipzig, 1995)
[7] De Bruyn B (2006). Near polygons. Birkhäuser Verlag, Basel Boston Berlin · Zbl 1102.51007
[8] De Clerck F and Van Maldeghem H (1995). Some classes of rank 2 geometries: handbook of incidence geometry. Elsevier, Amsterdam, pp, 433–475 · Zbl 0823.51010
[9] De Wispelaere A (2005) Ovoids and spreads of finite classical generalized hexagons and applications. Ph.D. thesis, Ghent University
[10] El Zahar M and Sauer NW (1985). The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5: 121–126 · Zbl 0575.05028 · doi:10.1007/BF02579374
[11] Fiala NC, Haemers WH (2006) 5-chromatic strongly regular graphs. Discrete Math 306:3083–3096 · Zbl 1105.05074 · doi:10.1016/j.disc.2004.03.023
[12] Fon-Der-Flaass DG (1993). There exists no distance-regular graph with intersection array (5,4,3;1,1,2). Eur J Combin 14: 409–412 · Zbl 0794.05132 · doi:10.1006/eujc.1993.1045
[13] Garey MR, Johnson DS and Stockmeyer LJ (1976). Some NP-complete graph problems. Theor Comput Sci 1: 237–267 · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[14] Godsil CD (2004–2006) Interesting graphs and their colourings, unpublished notes 2004–2006. http://quoll.uwaterloo.ca/pstuff/colours.pdf
[15] Haemers WH (1979) Eigenvalue techniques in design and graph theory. Ph.D. thesis, Eindhoven University of Technology (http://alexandria.tue.nl/extra3/proefschrift/PRF3A/7909413.pdf) Also: Math Centre Tract 121, Mathematical Centre, Amsterdam, 1980 · Zbl 0429.05012
[16] Hoffman AJ (1970). On eigenvalues and colorings of graphs. In: Harris, B (eds) Graph theory and its applications, pp 79–91. Acad. Press, New York
[17] Ivanov AA and Shpectorov SV (1990). The P-geometry for M 23 has no nontrivial 2-coverings. Eur. J Combin 11: 373–379 · Zbl 0712.51009
[18] Payan C (1992). On the chromatic number of cube-like graphs. Discrete Math 103: 271–277 · Zbl 0772.05043 · doi:10.1016/0012-365X(92)90319-B
[19] Sokolová M (1987). The chromatic number of extended odd graphs is four.. Časopis Pěst Mat 112: 308–311 · Zbl 0667.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.