Coloring and Domination of Vertices in Triangle-free Graphs

被引：0
|
作者：
Dutton, Ronald [1 ]
机构：
[1] Department of Computer Science, University of Central Florida, Orlando,FL,32816, United States
来源：
Journal of Combinatorial Mathematics and Combinatorial Computing | 2019年 / 111卷
关键词：
Graph theory;
D O I：
暂无
中图分类号：
O144 [集合论]; O157 [组合数学（组合学）];
学科分类号：
070104 ;
摘要：
Any dominating set of vertices in a triangle-free graph can be used to specify a graph coloring with at most one color class more than the number of vertices in the dominating set. This bound is sharp for many graphs. Properties of graphs for which this bound is achieved are presented. © 2019 Charles Babbage Research Centre. All rights reserved.
引用
收藏
页码：137 / 143
相关论文
共 50 条
  • [31] Eternal Distance-k Domination on Graphs
    Cox D.
    Meger E.
    Messinger M.E.
    La Matematica, 2023, 2 (2): : 283 - 302
  • [32] On the Roman domination problem of some Johnson graphs
    Zec, Tatjana
    FILOMAT, 2023, 37 (07) : 2067 - 2075
  • [33] MINIMAL RAMSEY GRAPHS WITH MANY VERTICES OF SMALL DEGREE
    Boyadzhiyska, Simona
    Clemens, Dennis
    Gupta, Pranshu
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (03) : 1503 - 1528
  • [34] Breaking the degeneracy barrier for coloring graphs with no Kt minor
    Norin, Sergey
    Postle, Luke
    Song, Zi-Xia
    ADVANCES IN MATHEMATICS, 2023, 422
  • [35] Oriented 5-coloring of sparse plane graphs
    Borodin O.V.
    Ivanova A.O.
    Kostochka A.V.
    Journal of Applied and Industrial Mathematics, 2007, 1 (01) : 9 - 17
  • [36] k-frugal List Coloring of Sparse Graphs
    Fang Q.
    Zhang L.
    Tongji Daxue Xuebao/Journal of Tongji University, 2022, 50 (12): : 1825 - 1832
  • [37] 2-limited broadcast domination on grid graphs
    Slobodin, Aaron
    MacGillivray, Gary
    Myrvold, Wendy
    DISCRETE APPLIED MATHEMATICS, 2023, 338 : 158 - 178
  • [38] Incidence coloring numbers of two classes of planar graphs
    Department of Mathematics, Tongji University, Shanghai 200092, China
    不详
    不详
    Tongji Daxue Xuebao, 2008, 3 (392-396):
  • [39] Partitioning harary graphs into connected subgraphs containing prescribed vertices
    Baudon, Olivier
    Bensmail, Julien
    Sopena, Éric
    Sopena, Éric, 1600, Discrete Mathematics and Theoretical Computer Science (16): : 263 - 278
  • [40] Reducing the domination number of (P3 + kP2)-free graphs via one edge contraction
    Galby, E.
    Mann, F.
    Ries, B.
    DISCRETE APPLIED MATHEMATICS, 2021, 305 : 205 - 210
12345