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 条
  • [31] OBSTRUCTIONS FOR THREE-COLORING AND LIST THREE-COLORING H-FREE GRAPHS
    Chudnovsky, Maria
    Goedgebeur, Jan
    Schaudt, Oliver
    Zhong, Mingxian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (01) : 431 - 469
  • [32] Injective coloring of some subclasses of bipartite graphs and chordal graphs
    Panda, B. S.
    Priyamvada
    DISCRETE APPLIED MATHEMATICS, 2021, 291 : 68 - 87
  • [33] On the Minimum Sum Coloring of P 4-Sparse Graphs
    Bonomo, Flavia
    Valencia-Pabon, Mario
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 303 - 314
  • [34] On the Minimum Sum Coloring of P4-Sparse Graphs
    Flavia Bonomo
    Mario Valencia-Pabon
    Graphs and Combinatorics, 2014, 30 : 303 - 314
  • [35] On-line coloring of sparse random graphs and random trees
    Pittel, B
    Weishaar, RS
    JOURNAL OF ALGORITHMS, 1997, 23 (01) : 195 - 205
  • [36] Coloring of Some Crown-Free Graphs
    Wu, Di
    Xu, Baogang
    GRAPHS AND COMBINATORICS, 2023, 39 (05)
  • [37] Coloring of Some Crown-Free Graphs
    Di Wu
    Baogang Xu
    Graphs and Combinatorics, 2023, 39
  • [38] On total and edge coloring some Kneser graphs
    de Figueiredo, C. M. H.
    Patrao, C. S. R.
    Sasaki, D.
    Valencia-Pabon, M.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (01) : 119 - 135
  • [39] List 3-Coloring Graphs with No Induced P6 + rP3
    Chudnovsky, Maria
    Huang, Shenwei
    Spirkl, Sophie
    Zhong, Mingxian
    ALGORITHMICA, 2021, 83 (01) : 216 - 251
  • [40] Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
    Dantas, S
    Gravier, S
    Maffray, F
    DISCRETE APPLIED MATHEMATICS, 2004, 141 (1-3) : 93 - 101
12345