The computational complexity of weighted vertex coloring for {P5, K2,3, K2,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}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P5, K2,3, K2,3}-free graphs. As usual, PÅ 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.
Details
Impact Metrics