Improving the extraction and expansion method for large graph coloring

Graph coloring is one of the most studied combinatorial optimization problems. This paper presents an improved extraction and expansion method (IE2COL), initially introduced in Wu and Hao (2012) [44]. IE2COL employs a forward independent set extraction strategy to reduce the initial graph GG. From the reduced graph, IE2COL triggers a backward coloring process which uses extracted independent sets as new color classes for intermediate subgraph coloring. The proposed method is assessed on 20 large benchmark graphs with 900 to 4000 vertices. Computational results show that it provides new upper bounds for 6 graphs and consistently matches the current best-known results for 12 other graphs.