The b-Chromatic Number of Cubic Graphs

被引：0
|
作者：
Marko Jakovac
Sandi Klavžar
机构：
[1] University of Maribor,Faculty of Natural Sciences and Mathematics
[2] University of Ljubljana,Faculty of Mathematics and Physics
来源：
Graphs and Combinatorics | 2010年 / 26卷
关键词：
Chromatic number; b-Chromatic number; Cubic graph; Petersen graph; 05C15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The b-chromatic number of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex adjacent to some vertex in all the other color classes. It is proved that with four exceptions, the b-chromatic number of cubic graphs is 4. The exceptions are the Petersen graph, K3,3, the prism over K3, and one more sporadic example on 10 vertices.
引用
收藏
页码：107 / 118
页数：11
相关论文
共 50 条
  • [1] The b-Chromatic Number of Cubic Graphs
    Jakovac, Marko
    Klavzar, Sandi
    GRAPHS AND COMBINATORICS, 2010, 26 (01) : 107 - 118
  • [2] On the b-chromatic number of Kneser graphs
    Hajiabolhassan, Hossein
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (03) : 232 - 234
  • [3] On the b-chromatic number of regular graphs
    Cabello, Sergio
    Jakovac, Marko
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (13) : 1303 - 1310
  • [4] The b-Chromatic Number of Corona Graphs
    Vivin, Vernold J.
    Venkatachalam, M.
    UTILITAS MATHEMATICA, 2012, 88 : 299 - 307
  • [5] Bounds for the b-chromatic number of some families of graphs
    Kouider, M
    Zaker, M
    DISCRETE MATHEMATICS, 2006, 306 (07) : 617 - 623
  • [6] On the b-chromatic number of rooted product graphs
    Bockting-Conrad, Sarah
    Jakovac, Marko
    Lang, Michael S.
    FILOMAT, 2025, 39 (11) : 3805 - 3815
  • [7] A Note on the b-Chromatic Number of Corona of Graphs
    Lisna, P. C.
    Sunitha, M. S.
    JOURNAL OF INTERCONNECTION NETWORKS, 2015, 15 (1-2)
  • [8] On the b-chromatic number of regular bounded graphs
    Amine, El Sahili
    Mekkia, Kouider
    Maidoun, Mortada
    DISCRETE APPLIED MATHEMATICS, 2015, 193 : 174 - 179
  • [9] The b-chromatic number of some power graphs
    Effantin, B
    Kheddouci, H
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2003, 6 (01): : 45 - 54
  • [10] The b-chromatic number of certain graphs and digraphs
    Kok, Johan
    Sudev, N. K.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2016, 19 (02) : 435 - 445
12345