A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring

Abstract

Given a graph $G$ and positive integers $b$ and $w$, the Black-and-White Coloring problem asks about the existence of a partial vertex-coloring of $G$, with $b$ vertices colored black and $w$ white, such that there is no edge between a black and a white vertex. The problem is known to be NP-complete.

In this paper, we deal with the optimization version, mainly for random graphs. Using the method of conditional expectations, we develop a heuristic with a good performance. We also obtain theoretical results on some of the relevant quantities, and compare the performance of the heuristic with that of several others.