b-coloring of Cartesian product of odd graphs

被引:0
作者
Balakrishnan, R. [1 ]
Raj, S. Francis [2 ]
Kavaskar, T. [1 ]
机构
[1] Bharathidasan Univ, Dept Math, Tiruchirappalli 620024, India
[2] Pondicherry Univ, Dept Math, Pondicherry 605014, India
关键词
b-coloring; b-continuity; Cartesian product; odd graphs; CHROMATIC NUMBER; BOUNDS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. The b-spectrum S-b(G) of a graph G is the set of positive integers k, chi(G) <= k <= b(G), for which G has a b-coloring using k colors. A graph G is b-continuous if S-b(G)= {chi(G),..., b(G)}. It is known that for any two graphs G and H, b(G square H) >= max{b(G), b(H)}, where square stands for the Cartesian product. In this paper, we determine some families of graphs G and H for which b(G square H) >= b(G) b(H) - 1. Further we show that if O-ki, i = 1,2,...,n are odd graphs with k(i) >= 4 for each i, then O-k1 square O-k2 square... square O-kn is b-continuous and b(O-k1 square O-k2 square ... square O-kn) = 1 + Sigma(n)(i=1) k(i).
引用
收藏
页码:285 / 298
页数:14
相关论文
共 17 条
  • [1] b-coloring of Kneser graphs
    Balakrishnan, R.
    Kavaskar, T.
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) : 9 - 14
  • [2] On the b-Coloring of Cographs and P4-Sparse Graphs
    Bonomo, Flavia
    Duran, Guillermo
    Maffray, Frederic
    Marenco, Javier
    Valencia-Pabon, Mario
    [J]. GRAPHS AND COMBINATORICS, 2009, 25 (02) : 153 - 167
  • [3] Effantin B, 2003, DISCRET MATH THEOR C, V6, P45
  • [4] Faik T., 2003, N1350 LRI U PAR
  • [5] Faik T., 2004, ELECT NOTES DISCRETE, V17, P151, DOI [10.1016/j.endm.2004.03.030, DOI 10.1016/J.ENDM.2004.03.030]
  • [6] On the b-chromatic number of Kneser graphs
    Hajiabolhassan, Hossein
    [J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (03) : 232 - 234
  • [7] Harary F., 1970, J COMB THEORY, V8, P154, DOI DOI 10.1016/S0021-9800(70)80072-2
  • [8] The b-chromatic number of a graph
    Irving, RW
    Manlove, DF
    [J]. DISCRETE APPLIED MATHEMATICS, 1999, 91 (1-3) : 127 - 141
  • [9] The b-Chromatic Number of Cubic Graphs
    Jakovac, Marko
    Klavzar, Sandi
    [J]. GRAPHS AND COMBINATORICS, 2010, 26 (01) : 107 - 118
  • [10] JAVADI R, ARS COMBINA IN PRESS