<p>I'm reading the <a href="https://dl.acm.org/doi/pdf/10.1145/167088.167149" rel="nofollow noreferrer">article</a> &quot;What can be computed locally?&quot; by Naor &amp; Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2)</p>
<p>An Locally Checkable Labelling (LCL) <span class="math-container">$\mathcal{L}$</span> consist of a positive integer <span class="math-container">$r$</span>, a set <span class="math-container">$\Sigma$</span> of input labels, a set <span class="math-container">$\Gamma$</span> of output labels and a set <span class="math-container">$\mathcal{C}$</span> of of locally consistent labels. Given a graph <span class="math-container">$G$</span> and <span class="math-container">$\lambda: V\mapsto \Sigma \times \Gamma$</span>, we say that <span class="math-container">$\lambda$</span> is <span class="math-container">$\mathcal{L}$</span>-legal if <span class="math-container">$\forall u \in V$</span>, there exists <span class="math-container">$(H,s) \in \mathcal{C}$</span> and an isomorphism <span class="math-container">$\pi$</span> mapping <span class="math-container">$B(u,r)$</span> to <span class="math-container">$H$</span> such that <span class="math-container">$\pi(u) = s$</span> and <span class="math-container">$\pi$</span> respect the labelling, i.e. for all label-pair <span class="math-container">$w$</span>, equals the label pair <span class="math-container">$\pi(w)$</span>.</p>
<p>Note: <span class="math-container">$(H,s)$</span> is a graph centered in <span class="math-container">$s$</span>, a.k.a. <span class="math-container">$s \in H$</span>.</p>
<p>I don't really understand some part of this definition, but mostly what <span class="math-container">$\mathcal{C}$</span> 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.</p>
<p>Suppose we need <span class="math-container">$c$</span> colors; so <span class="math-container">$\Gamma = [c]$</span>. Clearly <span class="math-container">$r=1$</span> as it is sufficient for nodes to check up to their direct neighbors. Now I'm not sure what <span class="math-container">$\Sigma$</span> can look like; I suspect in the case of coloration it is not really needed as this problem is too simple? As for <span class="math-container">$\mathcal{C}$</span> 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 <span class="math-container">$\pi$</span> fits in all this.</p>

CC BY-SA 4.0
2023-08-30T15:59:35.147Z
"I don't really understand ..." is hardly a research level question, which is what cstheory targets.
Kai
CC BY-SA 4.0
2023-08-30T16:00:31.040Z
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
<graph-theory><dc.distributed-comp>
Application LCL definition to vertex coloration
Qise
# Application LCL definition to vertex coloration

(Asked by: username_0 on 2023-08-16)

I'm reading the [article](https://dl.acm.org/doi/pdf/10.1145/167088.167149) "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.

**Tags:** graph-theory, dc.distributed-comp
> **Comments:**
> **username_1**: "I don't really understand ..." is hardly a research level question, which is what cstheory targets.  
> **username_1**: 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.  

---

## 0 answers

