On b-coloring of the Kneser graphs

被引：35

作者：

Javadi, Ramin ^{[1
]}

Omoomi, Behnaz ^{[1
]}

机构：

[1] Isfahan Univ Technol, Dept Math Sci, Esfahan 8415683111, Iran

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 13期

关键词：

b-chromatic number; b-coloring; Dominating coloring; b-continuous graph; Kneser graph; Steiner triple system; CHROMATIC NUMBER;

D O I：

10.1016/j.disc.2009.01.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A b-coloring of a graph G by k colors is a proper k-coloring of G such that in each color class there exists a vertex having neighbors in all the other k - 1 color classes. The b-chromatic number of a graph G, denoted by phi(G), is the maximum k for which G has a b-coloring by k colors. It is obvious that chi(G) <= phi(G). A graph G is b-continuous if for every k between chi(G) and phi(G) there is a b-coloring of G by k colors. In this paper, we study the b-coloring of Kneser graphs K(n, k) and determine phi(K(n, k)) for some values of n and k. Moreover, we prove that K(n, 2) is b-continuous for n >= 17. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：4399 / 4408

页数：10

共 8 条

[1] On the b-continuity property of graphs [J].