  We show an $\Omega\big(\Delta^{\frac{1}{3}-\frac{\eta}{3}}\big)$ lower bound
on the runtime of any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$-graph coloring algorithm in a weak
variant of the \LOCAL\ model.
  In particular, given a network graph \mbox{$G=(V,E)$}, in the weak \LOCAL\
model nodes communicate in synchronous rounds and they can use unbounded local
computation. We assume that the nodes have no identifiers, but that instead,
the computation starts with an initial valid vertex coloring. A node can
\textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its
neighbors and receives the \textbf{set of messages} sent to it by its
neighbors. That is, if two neighbors of a node $v\in V$ send the same message
to $v$, $v$ will receive this message only a single time; without any further
knowledge, $v$ cannot know whether a received message was sent by only one or
more than one neighbor.
  Neighborhood graphs have been essential in the proof of lower bounds for
distributed coloring algorithms, e.g., \cite{linial92,Kuhn2006On}. Our proof
analyzes the recursive structure of the neighborhood graph of the respective
model to devise an $\Omega\big(\Delta^{\frac{1}{3}-\frac{\eta}{3}}\big)$ lower
bound on the runtime for any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$-graph coloring algorithm.
  Furthermore, we hope that the proof technique improves the understanding of
neighborhood graphs in general and that it will help towards finding a lower
(runtime) bound for distributed graph coloring in the standard \LOCAL\ model.
Our proof technique works for one-round algorithms in the standard \LOCAL\
model and provides a simpler and more intuitive proof for an existing
$\Omega(\Delta^2)$ lower bound.
