Rank and chromatic number of a graph

被引：0
作者：
Kotlov, A
机构：
来源：
JOURNAL OF GRAPH THEORY | 1997年 / 26卷 / 01期
关键词：
rank; chromatic number; independence number;
D O I：
暂无
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It was proved (A. Kotlov and L. Lovasz, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O((root 2)(r)) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(Delta(r)) where Delta = 4/3 < root(2). (C) 1997 John Wiley & Sons, Inc.
引用
收藏
页码：1 / 8
页数：8
相关论文
共 11 条
[1]   A COUNTEREXAMPLE TO THE RANK-COLORING CONJECTURE [J].
ALON, N ;
SEYMOUR, PD .
JOURNAL OF GRAPH THEORY, 1989, 13 (04) :523-525
[2]   ON CONJECTURES OF GRAFFITI [J].
FAJTLOWICZ, S .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :113-118
[3]  
GRUBER PM, 1993, HDB CONVEX GEOMETRY, VB, P826
[4]  
Kabatyanskii G. A., 1978, PROBL PEREDACHI INF, V14, P3
[5]  
Kotlov A, 1996, J GRAPH THEOR, V23, P185, DOI 10.1002/(SICI)1097-0118(199610)23:2<185::AID-JGT9>3.0.CO
[6]  
2-P
[7]  
Lovasz L., 1990, Paths, flows, and VLSI-layout, P235
[8]  
Nisan N., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P831, DOI 10.1109/SFCS.1994.365711
[9]  
Raz R., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P168, DOI 10.1109/SFCS.1993.366870
[10]  
RAZBOROV A, 1982, DISCRETE MATH, V108, P393
12