Chromatic number and the 2-rank of a graph

被引：31
作者：
Godsil, CD [1 ]
Royle, GF
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[2] Univ Western Australia, Dept Comp Sci, Nedlands, WA 6009, Australia
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2001年 / 81卷 / 01期
关键词：
D O I：
10.1006/jctb.2000.2003
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (C) 2001 Academic Press.
引用
收藏
页码：142 / 149
页数：8
相关论文
共 20 条
[1]   A COUNTEREXAMPLE TO THE RANK-COLORING CONJECTURE [J].
ALON, N ;
SEYMOUR, PD .
JOURNAL OF GRAPH THEORY, 1989, 13 (04) :523-525
[2]  
ELLINGHAM MN, 1993, J COMBIN, V8, P247
[3]  
Garzon M. H., 1987, Journal of Combinatorial Mathematics and Combinatorial Computing, V2, P193
[4]  
Hoffman A. J., 1970, GRAPH THEORY ITS APP, P79, DOI DOI 10.1142/97898127969360041
[5]   SOME SIMPLE LIE-ALGEBRAS OF CHARACTERISTIC-2 [J].
KAPLANSKY, I .
LECTURE NOTES IN MATHEMATICS, 1982, 933 :127-129
[6]  
Kotlov A, 1996, J GRAPH THEOR, V23, P185, DOI 10.1002/(SICI)1097-0118(199610)23:2<185::AID-JGT9>3.0.CO
[7]  
2-P
[8]  
KOTLOV A, 1959, J GRAPH THOERY, V26, P1
[9]   Orthogonal representations over finite fields and the chromatic number of graphs [J].
Peeters, R .
COMBINATORICA, 1996, 16 (03) :417-431
[10]  
PEETERS R, 1995, THESIS TILBORG U
12