Paper Title
The computational complexity of weighted vertex coloring for {P5, K2,3, K2,3}-free graphs
Journal
Research Impact Tools
Publication Info
Volume: 15 | Pages: 137–152
Published On
May, 2020
Downloads
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.
View more »