Probabilistic graph-coloring in bipartite and split graphs (Q732320)

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.