@article{Berend_Mamana_2024, title={A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2964}, DOI={10.7155/jgaa.v28i1.2964}, abstractNote={<p>Given a graph $G$ and positive integers $b$ and $w$, the <em>Black-and-White Coloring problem</em> 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.</p> <p>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.</p>}, number={1}, journal={Journal of Graph Algorithms and Applications}, author={Berend, Daniel and Mamana, Shaked}, year={2024}, month={Sep.}, pages={365–383} }