Probabilistic graph-coloring in bipartite and split graphs
The authors consider probabilistic coloring problems. In bipartite graphs some polynomially solvable cases are considered and some approximation results are given, using the standard- and the differential-approximation ratio. The authors show that probabilistic coloring is NP-hard in split graphs and that the existence of a fully polynomial time standard-approximation schema is impossible. However, they provide a polynomial time standard-approximation schema under any system of vertex-probabilities and a polynomial time differential-approximation schema under identical vertex-probabilities.
scientific article; zbMATH DE number 5612785
scientific article