Efficient list cost Coloring of vertices and/or edges of some sparse graphs

被引：0
作者：
Giaro, Krzysztof [1 ]
Kubale, Marek [1 ]
机构：
[1] Gdansk Univ Technol, Dept Algorithms & Syst Modeling, Gdansk, Poland
来源：
NUMERICAL ANALYSIS AND APPLIED MATHEMATICS | 2007年 / 936卷
关键词：
chromatic number; graph coloring; polynomial algorithm; tree;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers.
引用
收藏
页码：241 / +
页数：2
相关论文
共 50 条
  • [41] On the b-Coloring of Cographs and P4-Sparse Graphs
    Bonomo, Flavia
    Duran, Guillermo
    Maffray, Frederic
    Marenco, Javier
    Valencia-Pabon, Mario
    GRAPHS AND COMBINATORICS, 2009, 25 (02) : 153 - 167
  • [42] The coloring game on planar graphs with large girth, by a result on sparse cactuses
    Charpentier, Clement
    DISCRETE MATHEMATICS, 2017, 340 (05) : 1069 - 1073
  • [43] An improved upper bound for the dynamic list coloring of 1-planar graphs
    Hu, Xiaoxue
    Kong, Jiangxu
    AIMS MATHEMATICS, 2022, 7 (05): : 7337 - 7348
  • [44] List-Coloring Claw-Free Graphs with Small Clique Number
    Louis Esperet
    András Gyárfás
    Frédéric Maffray
    Graphs and Combinatorics, 2014, 30 : 365 - 375
  • [45] List-Coloring Claw-Free Graphs with Small Clique Number
    Esperet, Louis
    Gyarfas, Andras
    Maffray, Frederic
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 365 - 375
  • [46] SOME NEW RESULTS ON EQUITABLE COLORING PARAMETERS OF GRAPHS
    Sudev, N. K.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2020, 89 (01): : 109 - 122
  • [47] PACKING COLORING OF SOME UNDIRECTED AND ORIENTED CORONAE GRAPHS
    Laiche, Daouya
    Bouchemakh, Isma
    Sopena, Eric
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (03) : 665 - 690
  • [48] Grundy coloring in some subclasses of bipartite graphs and their complements
    Verma, Shaily
    Panda, B. S.
    INFORMATION PROCESSING LETTERS, 2020, 163
  • [49] b-Coloring of the Mycielskian of Some Classes of Graphs
    Raj, S. Francis
    Gokulnath, M.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (02) : 363 - 381
  • [50] ON b-COLORING OF CENTRAL GRAPH OF SOME GRAPHS
    Kalpana, M.
    Vijayalakshmi, D.
    COMMUNICATIONS FACULTY OF SCIENCES UNIVERSITY OF ANKARA-SERIES A1 MATHEMATICS AND STATISTICS, 2019, 68 (01): : 1229 - 1239
12345