Tales of Hoffman: Three extensions of Hoffman's bound on the graph chromatic number

被引：15

作者：

Bilu, Y ^{[1
]}

机构：

[1] Weizmann Inst Sci, Dept Mol Genet, IL-76100 Rehovot, Israel

[2] Hebrew Univ Jerusalem, IL-91905 Jerusalem, Israel

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2006年 / 96卷 / 04期

关键词：

graph chromatic number; vector chromatic number; Hoffman's bound; eigenvalues; positive semidefinite matrices;

D O I：

10.1016/j.jctb.2005.10.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Hoffman's bound on the chromatic number of a graph states that chi >= 1-lambda(1)/lambda(n). Here we show that the same bound, or slight modifications of it, hold for several graph parameters related to the chromatic number: the vector coloring number, the psi-covering number and the lambda-clustering number. (C) 2005 Elsevier Inc. All rights reserved.

引用

页码：608 / 613

页数：6