On the probabilistic minimum coloring and minimum image-coloring Original Research Article

We study a robustness model for the minimum coloring problem, where any vertex image of the input-graph image has some presence probability image. We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of image into independent sets image, that minimizes the quantity image, where, for any independent set image, image. We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min image-Coloring) is NP-hard, for any image. We finally study Probabilistic Min Coloring and Probabilistic Min image-Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs.