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 条
  • [21] Incidence coloring of the squares of some graphs
    Li, Deming
    Liu, Mingju
    DISCRETE MATHEMATICS, 2008, 308 (24) : 6569 - 6574
  • [22] SOME RESULTS ON T-COLORING AND ST-COLORING OF GENERALIZED BUTTERFLY GRAPHS
    Moran, Rubul
    Bora, Niranjan
    Pegu, Aditya
    Chamua, Monjit
    ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2022, 31 : 1 - 12
  • [23] Indicated coloring of some families of graphs
    Francis, P.
    Francis Raj, S.
    Gokulnath, M.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (03)
  • [24] List injective coloring of planar graphs with girth g ≥ 6
    Chen, Hong-Yu
    Wu, Jian-Liang
    DISCRETE MATHEMATICS, 2016, 339 (12) : 3043 - 3051
  • [25] Average-case complexity of backtrack search for coloring sparse random graphs
    Mann, Zoltan Adam
    Szajko, Aniko
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2013, 79 (08) : 1287 - 1301
  • [26] Equitable list-coloring for graphs for maximum Degree 3
    Pelsmajer, MJ
    JOURNAL OF GRAPH THEORY, 2004, 47 (01) : 1 - 8
  • [27] List star edge coloring of k-degenerate graphs
    Han, Miaomiao
    Li, Jiaao
    Luo, Rong
    Miao, Zhengke
    DISCRETE MATHEMATICS, 2019, 342 (06) : 1838 - 1848
  • [28] Obstructions for three-coloring graphs without induced paths on six vertices
    Chudnovsky, Maria
    Goedgebeur, Jan
    Schaudt, Oliver
    Zhong, Mingxian
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 140 : 45 - 83
  • [29] PROPERTIES OF SIMPLICIAL VERTICES IN SOME FUZZY GRAPHS
    Radha, K.
    Indumathi, P.
    ADVANCES AND APPLICATIONS IN MATHEMATICAL SCIENCES, 2021, 20 (05): : 905 - 916
  • [30] On the number of P-vertices of some graphs
    Andelic, Milica
    da Fonseca, C. M.
    Mamede, Ricardo
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 434 (02) : 514 - 525
12345