Degeneracy-Guided List Compression for Greedy Graph Coloring
Data Structures and Algorithms
Summary
The authors explore a new method, called P-SAPST, to make greedy graph coloring more efficient by using information about the graph's structure before assigning colors. Their approach orders vertices based on a reversed low-degree removal sequence and assigns color lists that depend on the vertex's local neighborhood. This leads to much smaller color lists needed for success compared to previous methods, especially on graphs with many hubs or power law distributions. They tested their method extensively and found it performs well in practice, reducing the average list size significantly while keeping a high success rate. The approach is especially useful offline where the graph structure is known in advance and can be leveraged.
Authors
Rong Fu, Yongtai Liu, Xiaowen Ma, Wangyu Wu, Long Zhang, Hongbo Zhang, Yangchen Zeng, Hoi Leong Lee, Hao Zhang
Abstract
We study degeneracy guided list compression for greedy graph coloring when graph structure is available before colors are sampled. Our exposure calibrated ordering framework assigns each vertex an independent uniform list according to its backward neighborhood in a color independent order. Its certified instantiation, Profiled Structure Aware Asymmetric Palette Sparsification, or P-SAPST, reverses a minimum degree removal sequence and obtains every backward exposure from the removal profile. For each fixed profile, we characterize the exact local budget required by independent uniform lists under history robust greedy recovery. The profile yields linear list volume on high degree forests and on a core fringe family where reciprocal rank allocation requires Theta(n log^2 n) sampled colors. Exact conflict expectation, concentration, and a dense exposure barrier complete the theoretical description. The evaluation contains 40,320 runs over SAPBench and two SNAP networks. At the theorem scale, P-SAPST reduces mean list size by 47.6 percent relative to calibrated APST while attaining 99.8 percent observed greedy success. P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework. On stress graphs with 250,000 vertices and up to 1,251,868 edges, Lite obtains a payload ratio of 0.865, while calibrated APST obtains 7.886. On email Enron, the corresponding ratios are 0.193 and 5.814. Compression is strongest on hub dominated and power law graphs and disappears near the dense exposure barrier. The method complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.