• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

The computational complexity of weighted vertex coloring for {P_5,K_{2,3},K_{2,3}^+}-free graphs

Optimization Letters. 2021. Vol. 15. No. 1. P. 137-152.

In this paper, we show that the weighted vertex coloring problem can be solved in polynomial on the sum of vertex weights time for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As usual, P_5 and K_{2,3} stands, respectively, for the simple path on 5 vertices and for the biclique with the parts of 2 and 3 vertices, K_{2,3} denotes the graph, obtained from a K_{2,3} by joining its degree 3 vertices with an edge.