EN|RU
English version: Journal of Applied and Industrial Mathematics, 2021, 15:1, 97-117 |
![]() |
Volume 28, No 1, 2021, P. 15-47 UDC 519.17
Keywords: weighted vertex coloring problem, hereditary class, com?putational complexity. DOI: 10.33048/daio.2021.28.685 Olga O. Razvenskaya 1 Received April 29, 2020 References[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).[2] D. Král’, J. Kratochvíl, Z. Tuza, and G. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, in Graph-Theoretic Concepts in Computer Science (Proc. 27th Int. Workshop, Boltenhagen, Germany, June 14–16, 2001) (Springer, Heidelberg, 2001), pp. 254–262 (Lect. Notes Comput. Sci., Vol. 2204). [3] V. V. Lozin and D. S. Malyshev, Vertex coloring of graphs with few obstructions, Discrete Appl. Math. 216, 273–280 (2017). [4] P. A. Golovach, M. Johnson, D. Paulusma, and J. Song, A survey on the computational complexity of coloring graphs with forbidden subgraphs, J. Graph Theory 84 (4), 331–363 (2017). [5] K. Cameron, S. Huang, I. Penev, and V. Sivaraman, The class of ($P_7, C_4, C_5$)-free graphs: Decomposition, algorithms, and $\chi$-boundedness, J. Graph Theory 93 (4), 503–552 (2019). [6] K. Cameron, M. da Silva, S. Huang, and K. Vuskovic, Structure and algorithms for (cap, even hole)-free graphs, Discrete Math. 341, 463–473 (2018). [7] Y. Dai, A. Foley, and C. Hoàng, On coloring a class of claw-free graphs: To the memory of Frédéric Maffray, Electron. Notes Theor. Comput. Sci. 346, 369–377 (2019). [8] D. Fraser, A. Hamela, C. Hoàng, K. Holmes, and T. LaMantia, Characterizations of ($4K_1, C_4, C_5$)-free graphs, Discrete Appl. Math. 231, 166–174 (2017). [9] C. Hoàng and D. Lazzarato, Polynomial-time algorithms for minimum weighted colorings of ($P_5, \overline{P}_5$)-free graphs and similar graph classes, Discrete Appl. Math. 186, 105–111 (2015). [10] T. Karthick, F. Maffray, and L. Pastor, Polynomial cases for the vertex coloring problem, Algorithmica 81 (3), 1053–1074 (2017). [11] D. S. Malyshev, The coloring problem for classes with two small obstructions, Optim. Lett. 8 (8), 2261–2270 (2014). [12] D. S. Malyshev, Two cases of polynomial-time solvability for the coloring problem, J. Comb. Optim. 31 (2), 833–845 (2016). [13] D. S. Malyshev, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Discrete Appl. Math. 47, 423–432 (2018). [14] D. S. Malyshev and O. O. Lobanova, Two complexity results for the vertex coloring problem, Discrete Appl. Math. 219, 158–166 (2017). [15] D. V. Gribanov, D. S. Malyshev, and D. B. Mokeev, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions, Diskretn. Anal. Issled. Oper. 27 (3), 71–87 (2020) [Russian] [J. Appl. Ind. Math. 14 (3), 480–489 (2020)]. [16] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164, 51–229 (2006). [17] M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, Ann. Discrete Math. 21, 325–356 (1984). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|