English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$colors using a simple greedy algorithm. Remarkably, recent work has shown thatone can find such a coloring even in the semi-streaming model. But, in reality,one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed,the celebrated \Brooks' theorem states that every (connected) graph besidecliques and odd cycles can be colored with $\Delta$ colors. Can we find a$\Delta$-coloring in the semi-streaming model as well?  We settle this key question in the affirmative by designing a randomizedsemi-streaming algorithm that given any graph, with high probability, eithercorrectly declares that the graph is not $\Delta$-colorable or outputs a$\Delta$-coloring of the graph.  The proof of this result starts with a detour. We first (provably) identifythe extent to which the previous approaches for streaming coloring fail for$\Delta$-coloring: for instance, all these approaches can handle streams withrepeated edges and they can run in $o(n^2)$ time -- we prove that neither ofthese tasks is possible for $\Delta$-coloring. These impossibility resultshowever pinpoint exactly what is missing from prior approaches when it comes to$\Delta$-coloring.  We then build on these insights to design a semi-streaming algorithm thatuses $(i)$ a novel sparse-recovery approach based on sparse-densedecompositions to (partially) recover the "problematic" subgraphs of the input-- the ones that form the basis of our impossibility results -- and $(ii)$ anew coloring approach for these subgraphs that allows for recoloring of othervertices in a controlled way without relying on local explorations or finding"augmenting paths" that are generally impossible for semi-streaming algorithms.We believe both these techniques can be of independent interest.

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring