Geodesic
Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 15-47.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, computational complexity. 
@article{DA_2021_28_1_a1,
     author = {O. O. Razvenskaya and D. S. Malyshev},
     title = {Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {15--47},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/}
}
TY  - JOUR
AU  - O. O. Razvenskaya
AU  - D. S. Malyshev
TI  - Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 15
EP  - 47
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/
LA  - ru
ID  - DA_2021_28_1_a1
ER  - 
%0 Journal Article
%A O. O. Razvenskaya
%A D. S. Malyshev
%T Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 15-47
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/
%G ru
%F DA_2021_28_1_a1
O. O. Razvenskaya; D. S. Malyshev. Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 15-47. http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/

[1] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NP-completeness, Freeman, New York, 1979, 338 pp. | MR | Zbl

[2] Král' D., Kratochvíl J., Tuza Z., Woeginger G., “Complexity of coloring graphs without forbidden induced subgraphs”, Graph-Theoretic Concepts in Computer Science, Proc. 27th Int. Workshop (Boltenhagen, Germany, June 14–16, 2001), Lect. Notes Comput. Sci., 2204, Springer, Heidelberg, 2001, 254–262 | DOI | MR | Zbl

[3] Lozin V. V., Malyshev D. S., “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216 (2017), 273–280 | DOI | MR | Zbl

[4] Golovach P. A., Johnson M., Paulusma D., Song J., “A survey on the computational complexity of coloring graphs with forbidden subgraphs”, J. Graph Theory, 84:4 (2017), 331–363 | DOI | MR | Zbl

[5] Cameron K., Huang S., Penev I., Sivaraman V., “The class of $(P_7,C_4,C_5)$-free graphs: Decomposition, algorithms, and $\chi$-boundedness”, J. Graph Theory, 93:4 (2019), 503–552 | DOI | MR

[6] Cameron K., da Silva M., Huang S., Vuskovic K., “Structure and algorithms for (cap, even hole)-free graphs”, Discrete Math., 341 (2018), 463–473 | DOI | MR | Zbl

[7] Dai Y., Foley A., Hoàng C., “On coloring a class of claw-free graphs: To the memory of Frédéric Maffray”, Electron. Notes Theor. Comput. Sci., 346 (2019), 369–377 | DOI

[8] Fraser D., Hamela A., Hoàng C., Holmes K., LaMantia T., “Characterizations of $(4K_1,C_4,C_5)$-free graphs”, Discrete Appl. Math., 231 (2017), 166–174 | DOI | MR | Zbl

[9] Hoàng C., Lazzarato D., “Polynomial-time algorithms for minimum weighted colorings of $(P_5,\overline{P}_5)$-free graphs and similar graph classes”, Discrete Appl. Math., 186 (2015), 105–111 | DOI | MR

[10] Karthick T., Maffray F., Pastor L., “Polynomial cases for the vertex coloring problem”, Algorithmica, 81:3 (2017), 1053–1074 | DOI | MR

[11] Malyshev D. S., “The coloring problem for classes with two small obstructions”, Optim. Lett., 8:8 (2014), 2261–2270 | DOI | MR | Zbl

[12] Malyshev D. S., “Two cases of polynomial-time solvability for the coloring problem”, J. Comb. Optim., 31:2 (2016), 833–845 | DOI | MR | Zbl

[13] Malyshev D. S., “The weighted coloring problem for two graph classes characterized by small forbidden induced structures”, Discrete Appl. Math., 47 (2018), 423–432 | DOI | MR

[14] Malyshev D. S., Lobanova O. O., “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166 | DOI | MR | Zbl

[15] 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”, J. Appl. Ind. Math., 14:3 (2020), 480-489 | DOI | MR | MR

[16] Chudnovsky M., Robertson N., Seymour P., Thomas R., “The strong perfect graph theorem”, Ann. Math., 164 (2006), 51–229 | DOI | MR | Zbl

[17] Grötschel M., Lovász L., Schrijver A., “Polynomial algorithms for perfect graphs”, Ann. Discrete Math., 21 (1984), 325–356 | MR | Zbl