The computational complexity of weighted vertex coloring for {P5,K2,3,K2,3+}-free graphs

被引:0
作者
Malyshev, D. S. [1 ]
Razvenskaya, O. O. [1 ]
Pardalos, P. M. [2 ]
机构
[1] Natl Res Univ Higher Sch Econ, 25-12 Bolshaja Pecherskaja Ulitsa, Nizhnii Novgorod 603155, Russia
[2] Univ Florida, 401 Weil Hall,POB 116595, Gainesville, FL 32611 USA
基金
俄罗斯科学基金会;
关键词
Coloring problem; Hereditary class; Computational complexity; ALGORITHMS;
D O I
10.1007/s11590-020-01593-0
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we show that the weighted vertex coloring problem can be solved in polynomial on the sum of vertex weights time for {P5,K2,3,K2,3+}{P_5,K_{2,3}, K<^>+_{2,3}\}$$\end{document}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P5,K2,3,K2,3+}P_5,K_{2,3},K<^>+_{2,3}\}$$\end{document}-free graphs. As usual, P5 and K2,3 stands, respectively, for the simple path on 5 vertices and for the biclique with the parts of 2 and 3 vertices, K2,3+ denotes the graph, obtained from a K2,3 by joining its degree 3 vertices with an edge.
引用
收藏
页码:137 / 152
页数:16
相关论文
共 26 条
  • [11] 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
  • [12] Coloring graphs characterized by a forbidden subgraph
    Golovach, Petr A.
    Paulusma, Daniel
    Ries, Bernard
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 180 : 101 - 110
  • [13] Complexity of coloring graphs without paths and cycles
    Hell, Pavol
    Huang, Shenwei
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 216 : 211 - 232
  • [14] 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
  • [15] Polynomial Cases for the Vertex Coloring Problem
    Karthick, T.
    Maffray, Frederic
    Pastor, Lucas
    [J]. ALGORITHMICA, 2019, 81 (03) : 1053 - 1074
  • [16] A coloring problem on the n-cube
    Kim, DS
    Du, DZ
    Pardalos, PM
    [J]. DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) : 307 - 311
  • [17] Kral D., 2001, LECT NOTES COMPUT SC, V2001, P254, DOI DOI 10.1007/3-540-45477-223
  • [18] Vertex coloring of graphs with few obstructions
    Lozin, V. V.
    Malyshev, D. S.
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 216 : 273 - 280
  • [19] The weighted coloring problem for two graph classes characterized by small forbidden induced structures
    Malyshev, D. S.
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 247 : 423 - 432
  • [20] Polynomial-time approximation algorithms for the coloring problem in some cases
    Malyshev, D. S.
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (03) : 809 - 813