zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Chromatic number and the 2-rank of a graph. (English) Zbl 1026.05046
Summary: We show that if the adjacency matrix of a graph $X$ has 2-rank $2r$, then the chromatic number of $X$ is at most $2^r+ 1$, and that this bound is tight.

MSC:
05C15Coloring of graphs and hypergraphs
05C50Graphs and linear algebra
WorldCat.org
Full Text: DOI
References:
[1] Alon, N.; Seymour, P. D.: A counterexample to the rank-coloring conjecture. J. graph theory 13, 523-525 (1989) · Zbl 0674.05029
[2] Ellingham, M. N.: Basic subgraphs and graph spectra. Australas. J. Combin. 8, 247-265 (1993) · Zbl 0790.05057
[3] Garzon, M.: Symplectic embeddings of graphs. J. combin. Math. combin. Comput. 2, 193-207 (1987) · Zbl 0636.05045
[4] Hoffman, A. J.: On eigenvalues and colorings of graphs. (1970) · Zbl 0221.05061
[5] Kaplansky, I.: Some simple Lie algebras of characteristic 2. Lecture notes in mathematics 933 (1982) · Zbl 0493.17005
[6] Kotlov, A.; Lovasz, L.: The rank and size of graphs. J. graph theory 23, 185-189 (1996) · Zbl 0858.05060
[7] Kotlov, A.: Rank and chromatic number of a graph. J. graph theory 26, 1-8 (1997) · Zbl 0878.05033
[8] Peeters, R.: Ranks and structure of graphs. (1995) · Zbl 0820.05062
[9] Peeters, R.: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16, 417-431 (1996) · Zbl 0862.05040
[10] Raz, R.; Spieker, B.: On the ”\log rank”-conjecture in communication complexity. Combinatorica 15, 567-588 (1995) · Zbl 0845.68050
[11] Razborov, A. A.: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Discrete math. 108, 393-396 (1992) · Zbl 0776.05073
[12] Rotman, J. J.; Weichsel, P. M.: Simple Lie algebras and graphs. J. algebra 169, 775-790 (1994) · Zbl 0823.17008
[13] Seidel, J. J.: T.H.-report. (1973)
[14] Seidel, J. J.: D.g.corneilr.mathongeometry and combinatorics. Selected works of J. J. seidel. Geometry and combinatorics. Selected works of J. J. seidel (1991) · Zbl 0770.05001
[15] Shult, E.: Characterizations of certain classes of graphs. J. combinatorial theory ser. 13, 142-167 (1972) · Zbl 0227.05110
[16] Shult, E.: Graphs with geometric properties. J. combin. Math. combin. Comput. 19, 65-92 (1995) · Zbl 0842.05086
[17] Taylor, D. E.: The geometry of the classical groups. Sigma series in pure mathematics 9 (1992) · Zbl 0767.20001
[18] Thas, J. A.: Ovoids and spreads of finite classical polar spaces. Geom. dedicata 10, 135-143 (1981) · Zbl 0458.51010
[19] Van Nuffelen, C.: The rank of the adjacency matrix of a graph. Bull. soc. Math. belg. Sér. B 35, 219-225 (1983) · Zbl 0526.05040