Probabilistic graph-coloring in bipartite and split graphs (Exented version of cahier du LAMSADE 218)

Overview & Synopsis

We revisit in this paper the stochastic model for minimum graph-coloring introduced in (C. Murat and V. Th. Paschos, On the probabilistic minimum coloring and minimum k-coloring, Discrete Applied Mathematics 154, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standardapproximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standardapproximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P = NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs.