Application LCL definition to vertex coloration

I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2)

An Locally Checkable Labelling (LCL) $$\mathcal{L}$$ consist of a positive integer $$r$$, a set $$\Sigma$$ of input labels, a set $$\Gamma$$ of output labels and a set $$\mathcal{C}$$ of of locally consistent labels. Given a graph $$G$$ and $$\lambda: V\mapsto \Sigma \times \Gamma$$, we say that $$\lambda$$ is $$\mathcal{L}$$-legal if $$\forall u \in V$$, there exists $$(H,s) \in \mathcal{C}$$ and an isomorphism $$\pi$$ mapping $$B(u,r)$$ to $$H$$ such that $$\pi(u) = s$$ and $$\pi$$ respect the labelling, i.e. for all label-pair $$w$$, equals the label pair $$\pi(w)$$.

Note: $$(H,s)$$ is a graph centered in $$s$$, a.k.a. $$s \in H$$.

I don't really understand some part of this definition, but mostly what $$\mathcal{C}$$ looks like. I tried to think of a simple exemple: classic vertex coloration where you don't allow to neighbors to have the same colors.

Suppose we need $$c$$ colors; so $$\Gamma = [c]$$. Clearly $$r=1$$ as it is sufficient for nodes to check up to their direct neighbors. Now I'm not sure what $$\Sigma$$ can look like; I suspect in the case of coloration it is not really needed as this problem is too simple? As for $$\mathcal{C}$$ my guess is that it should include the informations relative to all the vertices and their direct neighbors, but I don't see how and what $$\pi$$ fits in all this.

• "I don't really understand ..." is hardly a research level question, which is what cstheory targets.
– Kai
Aug 30, 2023 at 15:59
• Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
– Kai
Aug 30, 2023 at 16:00