Voir la notice de l'article provenant de la source Math-Net.Ru
@article{DA_2020_27_3_a3, author = {D. V. Gribanov and D. S. Malyshev and D. B. Mokeev}, title = {Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions}, journal = {Diskretnyj analiz i issledovanie operacij}, pages = {71--87}, publisher = {mathdoc}, volume = {27}, number = {3}, year = {2020}, language = {ru}, url = {http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/} }
TY - JOUR AU - D. V. Gribanov AU - D. S. Malyshev AU - D. B. Mokeev TI - Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions JO - Diskretnyj analiz i issledovanie operacij PY - 2020 SP - 71 EP - 87 VL - 27 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/ LA - ru ID - DA_2020_27_3_a3 ER -
%0 Journal Article %A D. V. Gribanov %A D. S. Malyshev %A D. B. Mokeev %T Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions %J Diskretnyj analiz i issledovanie operacij %D 2020 %P 71-87 %V 27 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/ %G ru %F DA_2020_27_3_a3
D. V. Gribanov; D. S. Malyshev; D. B. Mokeev. Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 71-87. http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/
[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl
[2] D. Král', J. Kratochvíl, Z. Tuza, G. Woeginger, “Complexity of coloring graphs without forbidden induced subgraphs”, Proc. 27th Int. Workshop Graph-Theoretic Concepts in Computer Science (Boltenhagen, Germany, June 14–16, 2001), Lect. Notes Comput. Sci., 2204, Springer, Heidelberg, 2001, 254–262 | DOI | MR | Zbl
[3] V. V. Lozin, D. S. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216 (2017), 273–280 | DOI | MR | Zbl
[4] D. S. Malyshev, “Polynomial-time approximation algorithms for the coloring problem in some cases”, J. Comb. Optim., 33:3 (2017), 809–813 | DOI | MR | Zbl
[5] K. Dabrowski, P. A. Golovach, D. Paulusma, “Colouring of graphs with Ramsey-type forbidden subgraphs”, Theor. Comput. Sci., 522 (2014), 34–43 | DOI | MR | Zbl
[6] K. Dabrowski, V. V. Lozin, R. Raman, B. Ries, “Colouring vertices of triangle-free graphs without forests”, Discrete Math., 312:7 (2012), 1372–1385 | DOI | MR | Zbl
[7] P. A. Golovach, M. Johnson, D. Paulusma, J. Song, “A survey on the computational complexity of coloring graphs with forbidden subgraphs”, J. Graph Theory, 84 (2017), 331–363 | DOI | MR | Zbl
[8] P. A. Golovach, D. Paulusma, B. Ries, “Coloring graphs characterized by a forbidden subgraph”, Discrete Appl. Math., 180 (2015), 101–110 | DOI | MR | Zbl
[9] C. Hoàng, D. Lazzarato, “Polynomial-time algorithms for minimum weighted colorings of $(P5, \overline{P}5)$-free graphs and similar graph classes”, Discrete Appl. Math., 186 (2015), 105–111 | DOI | MR
[10] T. Karthick, F. Maffray, L. Pastor, “Polynomial cases for the vertex coloring problem”, Algorithmica, 81:3 (2017), 1053–1074 | DOI | MR
[11] D. S. Malyshev, “The coloring problem for classes with two small obstructions”, Optim. Lett., 8:8 (2014), 2261–2270 | DOI | MR | Zbl
[12] D. S. Malyshev, “Two cases of polynomial-time solvability for the coloring problem”, J. Comb. Optim., 31:2 (2015), 833–845 | DOI | MR
[13] D. S. Malyshev, “The weighted coloring problem for two graph classes characterized by small forbidden induced structures”, Discrete Appl. Math., 247 (2018), 423–432 | DOI | MR | Zbl
[14] D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166 | DOI | MR | Zbl
[15] A. Cournier, M. Habib, “A new linear algorithm for modular decomposition”, Trees in Algebra and Programming, CAAP-94, Proc. 19th Int. Colloq. (Edinburgh, UK, Apr. 11–13, 1994), Lect. Notes Comput. Sci., 787, Springer, Heidelberg, 1994, 68–84 | DOI | MR | Zbl
[16] R. E. Tarjan, “Decomposition by clique separators”, Discrete Math., 55:2 (1985), 221–232 | DOI | MR | Zbl
[17] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, “The strong perfect graph theorem”, Ann. Math., 164 (2006), 51–229 | DOI | MR | Zbl
[18] M. Grötschel, L. Lovász, A. Schrijver, “Polynomial algorithms for perfect graphs”, Ann. Discrete Math., 21 (1984), 325–356 | MR | Zbl