Efficient Solvability of the Weighted Vertex Coloring Problem for Some Hereditary Class of Graphs with $$\boldsymbol {5}$$ -Vertex Prohibitions
| Autor: | Dmitriy S. Malyshev, D. B. Mokeev, D. V. Gribanov |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computational complexity theory
Applied Mathematics 02 engineering and technology Disjoint sets 01 natural sciences Industrial and Manufacturing Engineering Graph Vertex (geometry) 010101 applied mathematics Combinatorics 020303 mechanical engineering & transports 0203 mechanical engineering Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0101 mathematics Coloring problem ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Applied and Industrial Mathematics. 14:480-489 |
| ISSN: | 1990-4797 1990-4789 |
| DOI: | 10.1134/s1990478920030072 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink