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 条
  • [41] A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture
    Leidner, Maxfield
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 377 - 388
  • [42] A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture
    Maxfield Leidner
    Graphs and Combinatorics, 2014, 30 : 377 - 388
  • [43] MATCHED-FACTOR d-DOMATIC COLORING OF GRAPHS
    Sudeep, K. S.
    Vishwanathan, Sundar
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 21 (04) : 1071 - 1082
  • [44] Compositions, decompositions, and conformability for total coloring on power of cycle graphs
    Zorzi, A.
    Figueiredo, C. M. H.
    Machado, R. C. S.
    Zatesko, L. M.
    Souza, U. S.
    DISCRETE APPLIED MATHEMATICS, 2022, 323 : 349 - 363
  • [45] EFFICIENT ALGORITHMS FOR THE DOMINATION PROBLEMS ON INTERVAL AND CIRCULAR ARC GRAPHS
    CHANG, MS
    IFIP TRANSACTIONS A-COMPUTER SCIENCE AND TECHNOLOGY, 1992, 12 : 402 - 408
  • [46] Independent domination in subcubic bipartite graphs of girth at least six
    Henning, Michael A.
    Löwenstein, Christian
    Rautenbach, Dieter
    Discrete Applied Mathematics, 2014, 162 : 399 - 403
  • [47] On the 2-rainbow independent domination numbers of some graphs
    Boštjan Gabrovšek
    Aljoša Peperko
    Janez Žerovnik
    Central European Journal of Operations Research, 2023, 31 (3) : 817 - 831
  • [48] On the 2-rainbow independent domination numbers of some graphs
    Gabrovsek, Bostjan
    Peperko, Aljosa
    Zerovnik, Janez
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2023, 31 (03) : 817 - 831
  • [49] New restrictions on defective coloring with applications to steinberg-type graphs
    Armstrong, Addie
    Eaton, Nancy
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (01) : 181 - 204
  • [50] On total coloring the direct product of cycles and bipartite direct product of graphs
    Castonguay, D.
    de Figueiredo, C. M. H.
    Kowada, L. A. B.
    Patrao, C. S. R.
    Sasaki, D.
    DISCRETE MATHEMATICS, 2023, 346 (06)
12345