Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:3, 480-489
Volume 27, No 3, 2020, P. 71-87
UDC 519.17
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
Abstract:
We consider the problem of minimizing the number of colors in the colorings of the vertices of a given graph so that, to each vertex there is assigned some set of colors whose number is equal to the given weight of the vertex; and adjacent vertices receive disjoint sets. For all hereditary classes defined by a pair of forbidden induced connected subgraphs on 5 vertices but four cases, the computational complexity of the weighted vertex coloring problem with unit weights is known. We prove the polynomial solvability on the sum of the vertex weights for this problem and the intersection of two of the four open cases. We hope that our result will be helpful in resolving the computational complexity of the weighted vertex coloring problem in the above-mentioned forbidden subgraphs.
Illustr. 1, bibliogr. 18.
Keywords: weighted vertex coloring problem, hereditary class, computational complexity.
DOI: 10.33048/daio.2020.27.668
Dmitry V. Gribanov 1,2
Dmitry S. Malyshev 1,2
Dmitry B. Mokeev 2,1
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
2. Lobachevsky State University of Nizhny Novgorod,
23 Gagarin Avenue, 603950 Nizhny Novgorod, Russia
e-mail: dimitry.gribanov@gmail.com, dsmalyshev@rambler.ru, mokeevdb@gmail.com
Received July 25, 2019
Revised January 6, 2020
Accepted February 19, 2020
References
[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).[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] D. S. Malyshev, Polynomial-time approximation algorithms for the coloring problem in some cases, J. Comb. Optim. 33 (3), 809–813 (2017).
[5] K. Dabrowski, P. A. Golovach, and D. Paulusma, Colouring of graphs with Ramsey-type forbidden subgraphs, Theor. Comput. Sci. 522, 34–43 (2014).
[6] K. Dabrowski, V. V. Lozin, R. Raman, and B. Ries, Colouring vertices of triangle-free graphs without forests, Discrete Math. 312, 1372–1385 (2012).
[7] 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, 331–363 (2017).
[8] P. A. Golovach, D. Paulusma, and B. Ries, Coloring graphs characterized by a forbidden subgraph, Discrete Appl. Math. 180, 101–110 (2015).
[9] C. Hoàng and D. Lazzarato, Polynomial-time algorithms for minimum weighted colorings of ($P_5$, $\bar{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–2702 (2014).
[12] D. S. Malyshev, Two cases of polynomial-time solvability for the coloring problem, J. Comb. Optim. 31 (2), 833–845 (2015).
[13] D. S. Malyshev, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Discrete Appl. Math. 247, 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] A. Cournier and M. Habib, A new linear algorithm for modular decomposition, in Trees in Algebra and Programming – CAAP’94 (Proc. 19th Int. Colloq., Edinburgh, UK, Apr. 11–13, 1994) (Springer, Heidelberg, 1994), pp. 68–84 (Lect. Notes Comput. Sci., Vol. 787).
[16] R. E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (2), 221–232 (1985).
[17] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164, 51–229 (2006).
[18] M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, Ann. Discrete Math. 21, 325–356 (1984).
