@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 = {graph partition, independent set, 2-colorable graph, approximation algorithm},
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.}
}