Coloring in Graph Streams

Decomposition of finite graphs into forests

CSJA Nash-Williams · 1964

Earlier work this paper cites.

The point-arboricity of a graph

Gary Chartrand, Hudson V Kronk, and Curtiss E Wall · 1968

Earlier work this paper cites.

Zero knowledge and the chromatic number

Uriel Feige and Joe Kilian · 1996

Earlier work this paper cites.

On graph problems in a semi-streaming model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang · 2004

Earlier work this paper cites.

Data streams: Algorithms and applications

S. Muthukrishnan · 2005

Earlier work this paper cites.

Better inapproximability results for maxclique, chromatic number and min-3lin-deletion

Subhash Khot and Ashok Kumar Ponnuswami · 2006

Earlier work this paper cites.

Distributed coloring in õ (√ log n) bit rounds

Kishore Kothapalli, Christian Scheideler, Melih Onus, and Christian Schindelhauer · 2006

Earlier work this paper cites.

Linear degree extractors and the inapproximability of max clique and chromatic number

David Zuckerman · 2006

Earlier work this paper cites.

On the decentralized dynamic graph coloring problem

Antoine Dutot, Frédéric Guinand, Damien Olivier, and Yoann Pigné · 2007

Cited alongside, same era.

Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition

Leonid Barenboim and Michael Elkin · 2010

Cited alongside, same era.

A new technique for distributed symmetry breaking

Johannes Schneider and Roger Wattenhofer · 2010

Cited alongside, same era.

Greedy algorithms for dynamic graph coloring

Linda Ouerfelli and Hend Bouziri · 2011

Cited alongside, same era.

Densest subgraph in streaming and mapreduce

Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii · 2012

Cited alongside, same era.

Distributed graph coloring: Fundamentals and recent developments

Leonid Barenboim and Michael Elkin · 2013

Cited alongside, same era.

Hypergraph two-coloring in the streaming model

Original

Jaikumar Radhakrishnan, Saswata Shannigrahi, and Rakesh Venkat · 2015

Later among the works it cites.

The locality of distributed symmetry breaking

Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider · 2016

Later among the works it cites.

Graph colouring as a challenge problem for dynamic graph processing on distributed systems

Scott Sallinen, Keita Iwabuchi, Suraj Poudel, Maya Gokhale, Matei Ripeanu, and Roger Pearce · 2016

Later among the works it cites.

Dynamic graph coloring

Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, and Sander Verdonschot · 2017

Later among the works it cites.

Fully-dynamic graph algorithms with sublinear time inspired by distributed computing

Leonid Barenboim and Tzalik Maimon · 2017

Later among the works it cites.