- Δ-Vertex Coloring in Graph Streams: Towards a Streaming
Brooks' Theorem
- Project Year:
2020
- REU Student (s):
Pankaj Kumar | Charles University (Prague, Czech Republic)
| Parth Mittal | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Sepehr Assadi
- Project Mentor Area:
Computer Science
- Project Abstract:
The celebrated Brooks' theorem in graph theory states that every connected graph which is not a clique nor an odd-cycle can be Δ colored; here Δis the maximum degree of the graph and we use n to denote the number of vertices. We investigate the possibility of obtaining a Δ-coloring via a space-efficient streaming algorithm. That is, an algorithm that makes one pass over the edges of the input graph while using a limited memory - much smaller than the input size which can be as large as Θ(n2) - and at the end of the stream, outputs a coloring of the input graph. Our main result is a randomized algorithm for this problem that uses O(n7/4) space.
