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 条
  • [41] b-Chromatic sum of a graph
    Lisna, P. C.
    Sunitha, M. S.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2015, 7 (04)
  • [42] b-chromatic numbers of powers of paths and cycles
    Lin, Wu-Hsiung
    Chang, Gerard J.
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2532 - 2536
  • [43] The difference between game chromatic number and chromatic number of graphs
    Matsumoto, Naoki
    INFORMATION PROCESSING LETTERS, 2019, 151
  • [44] On the chromatic number of random graphs
    Coja-Oghlan, Amin
    Panagiotou, Konstantinos
    Steger, Angelika
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (05) : 980 - 993
  • [45] On incompactness for chromatic number of graphs
    Shelah, S.
    ACTA MATHEMATICA HUNGARICA, 2013, 139 (04) : 363 - 371
  • [46] The Robust Chromatic Number of Graphs
    Bacso, Gabor
    Patkos, Balazs
    Tuza, Zsolt
    Vizer, Mate
    GRAPHS AND COMBINATORICS, 2024, 40 (04)
  • [47] On the chromatic number of Toeplitz graphs
    Nicoloso, Sara
    Pietropaoli, Ugo
    DISCRETE APPLIED MATHEMATICS, 2014, 164 : 286 - 296
  • [48] On group chromatic number of graphs
    Lai, HJ
    Li, XW
    GRAPHS AND COMBINATORICS, 2005, 21 (04) : 469 - 474
  • [49] Chromatic number and subtrees of graphs
    Baogang Xu
    Yingli Zhang
    Frontiers of Mathematics in China, 2017, 12 : 441 - 457
  • [50] Chromatic number and subtrees of graphs
    Xu, Baogang
    Zhang, Yingli
    FRONTIERS OF MATHEMATICS IN CHINA, 2017, 12 (02) : 441 - 457
12345