Parallel symmetry-breaking in sparse graphs

We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in Ο(lg^*n) time on an EREW PRAM ...

For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. ...

Let Δ denote the maximum degree of a graph. Fiamčík first, Alon, Sudakov and Zaks later conjectured that every graph is acyclically edge ( Δ + 2 ) -colorable. In this paper, we prove this conjecture for graphs with maximum average degree less than 4. As ...