Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2021, 15:1, 97-117
Volume 28, No 1, 2021, P. 15-47
UDC 519.17
O. O. Razvenskaya and D. S. Malyshev
Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
Abstract:
The weighted vertex coloring problem for a given weighted graph is to minimize the number of used colors so that for each vertex the number of the colors that are assigned to this vertex is equal to its weight and the assigned sets of vertices are disjoint for any adjacent vertices. For all but four hereditary classes that are defined by two connected 5-vertex induced prohibitions, the computational complexity is known of the weighted vertex coloring problem with unit weights. For four of the six pairwise intersections of these four classes, the solvability was proved earlier of the weighted vertex coloring problem in time polynomial in the sum of the vertex weights. Here we justify this fact for the remaining two intersections.
Bibliogr. 17.
Keywords: weighted vertex coloring problem, hereditary class, com?putational complexity.
DOI: 10.33048/daio.2021.28.685
Olga O. Razvenskaya 1
Dmitriy S. Malyshev 1
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
e-mail: olga-olegov@yandex.ru, dsmalyshev@rambler.ru
Received April 29, 2020
Revised November 3, 2020
Accepted November 5, 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).
