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 条
  • [1] An algorithm for 12-[5]coloring of triangle-free hexagonal graphs
    Zerovnik, J
    ITI 2005: PROCEEDINGS OF THE 27TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2005, : 673 - 678
  • [2] THE SPECTRUM OF TRIANGLE-FREE GRAPHS
    Balogh, Jozsef
    Clemen, Felix Christian
    Lidick, Bernard
    Norin, Sergey
    Volec, Jan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (02) : 1173 - 1179
  • [3] Large Cuts with Local Algorithms on Triangle-Free Graphs
    Hirvonen, Juho
    Rybicki, Joel
    Schmid, Stefan
    Suomela, Jukka
    ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (04)
  • [4] Exponentially many 4-list-colorings of triangle-free graphs on surfaces
    Kelly, Tom
    Postle, Luke
    JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 230 - 238
  • [5] On the NP-completeness of the k-colorability problem for triangle-free graphs
    Maffray, F
    Preissmann, M
    DISCRETE MATHEMATICS, 1996, 162 (1-3) : 313 - 317
  • [6] Image Classification of Leukemic Cells Using Invariants of Triangle-Free Graphs as Synthetic Features
    Muzalevskiy, Dmitry
    Torshin, Ivan
    IEEE ACCESS, 2024, 12 : 38551 - 38561
  • [7] Paired-Domination in Subdivided Star-Free Graphs
    Paul Dorbec
    Sylvain Gravier
    Graphs and Combinatorics, 2010, 26 : 43 - 49
  • [8] Paired-Domination in Subdivided Star-Free Graphs
    Dorbec, Paul
    Gravier, Sylvain
    GRAPHS AND COMBINATORICS, 2010, 26 (01) : 43 - 49
  • [9] Coloring fuzzy graphs
    Muñoz, S
    Ortuño, MT
    Ramírez, J
    Yáñez, J
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2005, 33 (03): : 211 - 221
  • [10] Roman domination in graphs
    Cockayne, EJ
    Dreyer, PA
    Hedetniemi, SM
    Hedetniemi, ST
    DISCRETE MATHEMATICS, 2004, 278 (1-3) : 11 - 22
12345