A Hybrid Approach for Exact Coloring of Massive Graphs

Abstract : The graph coloring problem appears in numerous applications, yet many state-of-the-art methods are hardly applicable to real world, very large, networks. The most efficient approaches for massive graphs rely on "peeling" the graph of its low-degree vertices and focus on the maximum k-core where k is some lower bound on the chromatic number of the graph. However, unless the graphs are extremely sparse, the cores can be very large, and lower and upper bounds are often obtained using greedy heuristics. In this paper, we introduce a combined approach using local search to find good quality solutions on massive graphs as well as locate small subgraphs with potentially large chromatic number. The subgraphs can be used to compute good lower bounds, which makes it possible to solve optimally extremely large graphs, even when they have large k-cores.
Complete list of metadatas

Contributor : Emmanuel Hebrard <>
Submitted on : Friday, March 22, 2019 - 9:29:21 AM
Last modification on : Monday, April 29, 2019 - 4:17:09 PM


Files produced by the author(s)


  • HAL Id : hal-02076298, version 1


Emmanuel Hébrard, George Katsirelos. A Hybrid Approach for Exact Coloring of Massive Graphs. Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019), Jun 2019, Thessaloniki, Greece. ⟨hal-02076298⟩



Record views


Files downloads