Name
Title | ||
|---|---|---|
The Computational Complexity Of Weighted Vertex Coloring For {P-5,K-2,K-3,K-2,3(+)}-Free Graphs |
Abstract | ||
|---|---|---|
In this paper, we show that the weighted vertex coloring problem can be solved in polynomial on the sum of vertex weights time for {P5,K2,3,K2,3+}{P_5,K_{2,3}, K<^>+_{2,3}\}$$\end{document}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P5,K2,3,K2,3+}P_5,K_{2,3},K<^>+_{2,3}\}$$\end{document}-free graphs. As usual, P5 and K2,3 stands, respectively, for the simple path on 5 vertices and for the biclique with the parts of 2 and 3 vertices, K2,3+ denotes the graph, obtained from a K2,3 by joining its degree 3 vertices with an edge. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s11590-020-01593-0 | OPTIMIZATION LETTERS |
Keywords | DocType | Volume |
Coloring problem, Hereditary class, Computational complexity | Journal | 15 |
Issue | ISSN | Citations |
1 | 1862-4472 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dmitriy S. Malyshev | 1 | 0 | 0.68 |
| O. O. Razvenskaya | 2 | 0 | 0.34 |
| Panos M. Pardalos | 3 | 141 | 19.60 |