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 条
  • [1] List star edge coloring of sparse graphs
    Kerdjoudj, Samia
    Raspaud, Andre
    DISCRETE APPLIED MATHEMATICS, 2018, 238 : 115 - 125
  • [2] Simultaneous coloring of vertices and incidences of outerplanar graphs
    Mozafari-Nia, Mahsa
    Iradmusa, Moharram N.
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2023, 11 (01) : 245 - 262
  • [3] A GRASP for Coloring Sparse Graphs
    Manuel Laguna
    Rafael Martí
    Computational Optimization and Applications, 2001, 19 : 165 - 178
  • [4] A GRASP for coloring sparse graphs
    Laguna, M
    Martí, R
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 19 (02) : 165 - 178
  • [5] Online list coloring for signed graphs
    Tupper, M.
    White, J. A.
    ALGEBRA AND DISCRETE MATHEMATICS, 2022, 33 (02): : 151 - 172
  • [6] List coloring of Cartesian products of graphs
    Borowiecki, Mieczyslaw
    Jendrol, Stanislav
    Kral, Daniel
    Miskuf, Jozef
    DISCRETE MATHEMATICS, 2006, 306 (16) : 1955 - 1958
  • [7] Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces
    Postle, Luke
    2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, : 929 - 941
  • [8] Critical vertices and edges in H-free graphs
    Paulusma, Daniel
    Picouleau, Christophe
    Ries, Bernard
    DISCRETE APPLIED MATHEMATICS, 2019, 257 : 361 - 367
  • [9] Acyclic list edge coloring of outerplanar graphs
    Shu, Qiaojun
    Wang, Yiqiao
    Wang, Weifan
    DISCRETE MATHEMATICS, 2013, 313 (03) : 301 - 311
  • [10] Strong spatial mixing of list coloring of graphs
    Gamarnik, David
    Katz, Dmitriy
    Misra, Sidhant
    RANDOM STRUCTURES & ALGORITHMS, 2015, 46 (04) : 599 - 613
12345