The weighted coloring problem for two graph classes characterized by small forbidden induced structures

被引：4
作者：
Malyshev, D. S. [1 ]
机构：
[1] Natl Res Univ, Higher Sch Econ, 25-12 Bolshaya Pecherskaya Ulitsa, Nizhnii Novgorod 603155, Russia
来源：
DISCRETE APPLIED MATHEMATICS | 2018年 / 247卷
基金：
俄罗斯基础研究基金会;
关键词：
Computational complexity; Coloring problem; Hereditary class; Polynomial-time algorithm;
D O I：
10.1016/j.dam.2018.04.006
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We show that the weighted coloring problem can be solved for {P-5, banner}-free graphs and for {P-5, dart}-free graphs in polynomial time on the sum of vertex weights. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：423 / 432
页数：10
相关论文
共 14 条
  • [1] The strong perfect graph theorem
    Chudnovsky, Maria
    Robertson, Neil
    Seymour, Paul
    Thomas, Robin
    [J]. ANNALS OF MATHEMATICS, 2006, 164 (01) : 51 - 229
  • [2] Colouring diamond-free graphs
    Dabrowski, Konrad K.
    Dross, Francois
    Paulusma, Daniel
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 89 : 410 - 431
  • [3] Colouring of graphs with Ramsey-type forbidden subgraphs
    Dabrowski, Konrad K.
    Golovach, Petr A.
    Paulusma, Daniel
    [J]. THEORETICAL COMPUTER SCIENCE, 2014, 522 : 34 - 43
  • [4] Colouring vertices of triangle-free graphs without forests
    Dabrowski, Konrad K.
    Lozin, Vadim
    Raman, Rajiv
    Ries, Bernard
    [J]. DISCRETE MATHEMATICS, 2012, 312 (07) : 1372 - 1385
  • [5] A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
    Golovach, Petr A.
    Johnson, Matthew
    Paulusma, Daniel
    Song, Jian
    [J]. JOURNAL OF GRAPH THEORY, 2017, 84 (04) : 331 - 363
  • [6] Coloring graphs characterized by a forbidden subgraph
    Golovach, Petr A.
    Paulusma, Daniel
    Ries, Bernard
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 180 : 101 - 110
  • [7] Grotschel M., 1984, ANN DISCRETE MATH, V21, P325, DOI [10.1016/S0304-0208(08)72943-8, DOI 10.1016/S0304-0208(08)72943-8]
  • [8] Polynomial-time algorithms for minimum weighted colorings of (P5, (P)over-bar5)-free graphs and similar graph classes
    Hoang, Chinh T.
    Lazzarato, D. Adam
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 186 : 106 - 111
  • [9] Kral D., 2001, LECT NOTES COMPUT SC, V2001, P254, DOI DOI 10.1007/3-540-45477-223
  • [10] Vertex coloring of graphs with few obstructions
    Lozin, V. V.
    Malyshev, D. S.
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 216 : 273 - 280
12