Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

Suman K. Bera, Amit Chakrabarti, Prantar Ghosh

We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model…