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 条
  • [1] The class of (P7,C4,C5)-free graphs: Decomposition, algorithms, and χ-boundedness
    Cameron, Kathie
    Huang, Shenwei
    Penev, Irena
    Sivaraman, Vaidy
    [J]. JOURNAL OF GRAPH THEORY, 2020, 93 (04) : 503 - 552
  • [2] Structure and algorithms for (cap, even hole)-free graphs
    Cameron, Kathie
    da Silva, Murilo V. G.
    Huang, Shenwei
    Vuskovic, Kristina
    [J]. DISCRETE MATHEMATICS, 2018, 341 (02) : 463 - 473
  • [3] On colouring (2P2, H)-free and (P5, H)-free graphs
    Dabrowski, Konrad K.
    Paulusma, Daniel
    [J]. INFORMATION PROCESSING LETTERS, 2018, 134 : 35 - 41
  • [4] Colouring diamond-free graphs
    Dabrowski, Konrad K.
    Dross, Francois
    Paulusma, Daniel
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 89 : 410 - 431
  • [5] Colouring of graphs with Ramsey-type forbidden subgraphs
    Dabrowski, Konrad K.
    Golovach, Petr A.
    Paulusma, Daniel
    [J]. THEORETICAL COMPUTER SCIENCE, 2014, 522 : 34 - 43
  • [6] 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
  • [7] On Coloring a Class of Claw-free Graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    [J]. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 369 - 377
  • [8] Foley A., ARXIV190408180
  • [9] Characterizations of (4K1, C4, C5)-free graphs
    Fraser, Dallas J.
    Hamel, Angele M.
    Hoang, Chinh T.
    Holmes, Kevin
    LaMantia, Tom P.
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 231 : 166 - 174
  • [10] Colouring square-free graphs without long induced paths
    Gaspers, Serge
    Huang, Shenwei
    Paulusma, Daniel
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2019, 106 : 60 - 79