  A Neighborhood Balanced Coloring (NBC) of a graph is a red-blue coloring
where each vertex has the same number of red and blue neighbors. This work
proves that determining if a graph admits an NBC is NP-complete. We present a
genetic algorithm to solve this problem, which we implemented and compared
against exact and randomized algorithms.
