NP-Completeness of Neighborhood Balanced Colorings
<|reference_start|>NP-Completeness of Neighborhood Balanced Colorings: 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.<|reference_end|>
@article{asaeedi2024np-completeness,
    title={NP-Completeness of Neighborhood Balanced Colorings},
    author={Saeed Asaeedi},
    journal={arXiv preprint arXiv:2407.19793},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.19793},
    primaryClass={cs.CC}
}