@article{Xie2023,
author = {Jingwei Xie and Yong Chen and An Zhang and Guangting Chen},
title = {Approximation Algorithms for Graph Partition into Bounded Independent Sets},
year = {2023},
journal = {Tsinghua Science and Technology},
volume = {28},
number = {6},
pages = {1063-1071},
keywords = {approximation algorithm, graph partition, independent set, 2-colorable graph},
url = {https://www.sciopen.com/article/10.26599/TST.2022.9010062},
doi = {10.26599/TST.2022.9010062},
abstract = {The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper. This problem is NP-hard, even restricted to bipartite graphs. First, a simple 32-approximation algorithm for any 2-colorable graph is presented. An improved 75-approximation algorithm is then designed for a tree. The theoretical proof of the improved algorithm performance ratio is constructive, thus providing an explicit partition approach for each case according to the cardinality of two color classes.}
}