$\Delta+1$-coloring in $O(\Delta^2+\log^*n)$ rounds.

Improvement: $O(\Delta+\log^*n)$

$O(\log^*n)$ rounds "cover-free families" to reduce colors from poly $n$ to $O(\Delta^2)$.
$O(\Delta)$ rounds "additive group coloring" to reduce from $O(\Delta^2)$ to $O(\Delta)$ colors.
$O(\Delta)$ rounds local minima algorithm to reduce from $O(\Delta)$ to $\Delta+1$.

Cover-Free Families

Instead of directly compute a new color in Cole-Vishkin, consider set as alternative formulation.

E.g. $x_v=1010,x_u=1001$, we use set of pairs: $$ s_v={(0,0),(1,1),(2,0),(3,1)},s_u={(0,1),(1,0),(2,0),(3,1)}. $$ Node $u$ sends $s_u$ to $v$, and $v$ picks the smallest element from $s_v\backslash s_u$.

So essentially, Cole-Vishkin is to map the color to the set of pairs.

Cover-Free

$\mathcal S$ is the $1$-cover-free family of sets if $$ \forall S,S'\in\mathcal S:S\backslash S'\neq\emptyset. $$ $\mathcal S$ is the $k$--cover-free family of sets if $$ \forall S,S_1,\cdots,S_k\in\mathcal S:S\backslash\cup_{i=1}^kS_i\neq\emptyset. $$

New Color Reduction Scheme

Assume $v$ is connected to $u,w,z$, which has the color $c_v\in C$.

In the first round, we want colors from $C'$.

Assume $\exist\Delta$-cover-free family $\mathcal S$ of sets s.t.,

$\vert\mathcal S\vert\geq\vert C\vert$, i.e., we can define an injective mapping from $C$ to $\mathcal S$.
$\forall S\in\mathcal S:S\subseteq C'$

Algorithm:

$v$ picks an element from $\mathcal S$ as a function of $c_v$.
Nodes exchange their sets.
$v$ picks an element $c'\in C'$ from $S_v\backslash(S_u\cup S_w\cup S_z)$.

How to Construct Cover-Free Families

We want $C'$ as small as possible and $\mathcal S$ as large as possible. But $\mathcal S$ are subsets of $C'$.

We want to pick many subsets of $C'$ s.t. they pairwise do not overlap much.

Construct $\mathcal S$ sets of size $q$ (prime) s.t. they pairwise overlap in at most $d$ elements s.t. $q>d\cdot\Delta(|\mathcal S|\geq|C|)$. Then $v$ can pick a color

Consider lines $y=ax+b$, each pair of non-parallel lines do not overlap much.

Each pair is $(a,b)$, evaluate these functions in $\{0,\cdots,q-1\}$.

How many times do they overlap? $\leq1$!

What if we modulo a prime $q$ then? Still $\leq1$!

Take $2$ polynomials $p_1,p_2$ of degree $d$, construct the sets $$ S_i={(0,p_i(0)),(1,p_i(1)),\cdots,(q-1,p_i(q-1))}, $$ how many elements $S_1$ and $S_2$ have in common? $\leq d$!

How many polynomials in total? $q^{d+1}$!

Thus, $\vert\mathcal S\vert=q^{d+1}$, $\Delta$-cover-free if $q>\Delta\cdot d$. $|C'|=q^2$.

If $|C|\leq q^{d+1}$ and $q>\Delta\cdot d$, then in $1$ round we can map colors to $C'$ s.t. $|C'|=q^2$.

Just fix parameters:

Pick $q$ smallest prime that $\Delta\cdot\log|C|\leq q\leq2\Delta\cdot\log|C|$,
Pick $d=\lfloor q/\Delta\rfloor$.

We start from $q^{d+1}$ colors: $q^{d+1}\geq 2^{d+1}\geq 2^{q/\Delta}\geq 2^{\log|C|}=|C|$.

We get $q^2$ colors then, $q^2\leq 4\Delta^2\log^2|C|$.

In one round, we can reduce colors from $C$ to $4\Delta^2\log^2|C|$.

So from poly $n$ to $O(\Delta^2\log^2\Delta)$, we have $O(\log^*n)$ rounds.

$\Delta^2\log^2\Delta\leq\Delta^3$.

Pick $d=2$, $10\Delta<q<20\Delta$. $q^{d+1}\ge(10\Delta)^3$, we get $q^2$ colors in $O(\Delta^2)$ rounds.

Additive-Group Coloring

$q^2$ colors can be represented by $q\times q$ coordinates.

Main Idea

Second entry is the target color.
If conflict, use the first entry (as speed) to change the second entry. (like a clock)

Algorithm

$q>2\Delta$, is a prime number.

Iterate

Send color to neighbors
If no conflict: stop clock (set the first entry to $0$)
If conflict: augment second entry by first (modulo $q$)

Complexity

How many conflict for a node $v$ in $q$ rounds? $\leq2\Delta$!

Lemma: Every node knows its final color after at most $q$ rounds.