Two cases of polynomial-time solvability for the coloring problem

被引：20
作者：
Malyshev, D. S. [1 ]
机构：
[1] Natl Res Univ, Higher Sch Econ, 25-12 Bolshaja Pecherskaja Ulitsa, Nizhnii Novgorod 603155, Russia
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2016年 / 31卷 / 02期
基金：
俄罗斯基础研究基金会;
关键词：
Vertex coloring; Computational complexity; Polynomial-time algorithm; K-COLORABILITY; GRAPHS;
D O I：
10.1007/s10878-014-9792-3
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes.
引用
收藏
页码：833 / 845
页数：13
相关论文
共 15 条
  • [1] A linear algorithm for maximum weight cliques in proper circular arc graphs
    Bhattacharya, B
    Hell, P
    Huang, J
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) : 274 - 289
  • [2] Colouring of graphs with Ramsey-type forbidden subgraphs
    Dabrowski, Konrad K.
    Golovach, Petr A.
    Paulusma, Daniel
    [J]. THEORETICAL COMPUTER SCIENCE, 2014, 522 : 34 - 43
  • [3] 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
  • [4] Golovach P, 2013, LIST COLORING ABSENC, P288
  • [5] GYARFAS A, 1987, ZASTOSOW MAT, V19, P413
  • [6] Deciding k-Colorability of P 5-Free Graphs in Polynomial Time
    Hoang, Chinh T.
    Kaminski, Marcin
    Lozin, Vadim
    Sawada, Joe
    Shu, Xiao
    [J]. ALGORITHMICA, 2010, 57 (01) : 74 - 81
  • [7] Boundary properties of graphs for algorithmic graph problems
    Korpelainen, Nicholas
    Lozin, Vadim V.
    Malyshev, Dmitriy S.
    Tiskin, Alexander
    [J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) : 3545 - 3554
  • [8] Kral D., 2001, LECT NOTES COMPUT SC, V2001, P254, DOI DOI 10.1007/3-540-45477-223
  • [9] Characterizations and recognition of circular-arc graphs and subclasses: A survey
    Lin, Min Chih
    Szwarcfiter, Jayme L.
    [J]. DISCRETE MATHEMATICS, 2009, 309 (18) : 5618 - 5635
  • [10] Lozin V, 2014, DISCRETE AP IN PRESS
12