<p>`Special labelling' is not exactly <span class="math-container">$L(0,1)$</span>-coloring, but is very close. In <span class="math-container">$L(0,1)$</span>-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name <em>injective coloring</em>.</p>
<blockquote>
<p>An injective colouring of a graph <span class="math-container">$G$</span> is a colouring <span class="math-container">$c$</span> of the vertices
of <span class="math-container">$G$</span> that assigns different colours to any pair of vertices that have a
common neighbour.</p>
</blockquote>
<p>There are a number of papers on injective coloring. The main graph classes studied are planar graphs [1,2,3], chordal graphs [4], regular graphs [5], and sparse graphs [6]</p>
<h2>References</h2>
<p>[1] <em>Bu, Yuehua; Qi, Chentao; Zhu, Junlei; Xu, Ting</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2021.01.007" rel="nofollow noreferrer"><strong>Injective coloring of planar graphs</strong></a>,  <a href="https://zbmath.org/?q=an:07300884" rel="nofollow noreferrer">ZBL07300884</a>.</p>
<p>[2] <em>Lužar, Borut; Škrekovski, Riste; Tancer, Martin</em>, <a href="http://dx.doi.org/10.1016/j.disc.2008.04.005" rel="nofollow noreferrer"><strong>Injective colorings of planar graphs with few colors</strong></a>, Discrete Math. 309, No. 18, 5636-5649 (2009). <a href="https://zbmath.org/?q=an:1209.05093" rel="nofollow noreferrer">ZBL1209.05093</a>.</p>
<p>[3] <em>Bu, Yuehua; Wang, Chao; Yang, Sheng</em>, List injective coloring of planar graphs.,  <a href="https://zbmath.org/?q=an:06986943" rel="nofollow noreferrer">ZBL06986943</a>.</p>
<p>[4] <em>Hell, Pavol; Raspaud, André; Stacho, Juraj</em>, <a href="http://dx.doi.org/10.1007/978-3-540-78773-0_45" rel="nofollow noreferrer"><strong>On injective colourings of chordal graphs</strong></a>, Laber, Eduardo Sany (ed.) et al., LATIN 2008 Berlin: Springer (ISBN 978-3-540-78772-3/pbk). LNCS 4957, 520-530 (2008). <a href="https://zbmath.org/?q=an:1136.68463" rel="nofollow noreferrer">ZBL1136.68463</a>.</p>
<p>[5] <em>Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique</em>, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00466-6" rel="nofollow noreferrer"><strong>On the injective chromatic number of graphs</strong></a>, Discrete Math. 256, No. 1-2, 179-192 (2002). <a href="https://zbmath.org/?q=an:1007.05046" rel="nofollow noreferrer">ZBL1007.05046</a>.</p>
<p>[6] <em>Cranston, Daniel W.; Kim, Seog-Jin; Yu, Gexin</em>, <a href="http://dx.doi.org/10.1016/j.disc.2010.07.003" rel="nofollow noreferrer"><strong>Injective colorings of sparse graphs</strong></a>, Discrete Math. 310, No. 21, 2965-2973 (2010). <a href="https://zbmath.org/?q=an:1209.05075" rel="nofollow noreferrer">ZBL1209.05075</a>.</p>

CC BY-SA 4.0
2021-04-02T09:26:29.720Z
2021-04-02T09:51:56.043Z
2021-04-02T09:51:56.043Z
Cyriac Antony
<p><span class="math-container">$L(p,q)$</span> coloring is a function V <span class="math-container">$\rightarrow \mathbb{N}$</span> such that the labels on vertices at distance 1 differ by at least <span class="math-container">$p$</span> and vertices at distance 2 differ by at least <span class="math-container">$q$</span>. Special labelling looks like <span class="math-container">$L(0,1)$</span> coloring.</p>

CC BY-SA 4.0
2021-03-22T08:42:45.317Z
Are you aware of any paper that give non-trivial resuts on $L(0,1)$-coloring?
Cyriac Antony
CC BY-SA 4.0
2021-03-21T18:35:03.780Z
2021-03-21T18:35:03.780Z
pradeesha ashok
<p><strong>Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?</strong><br />
A special labelling of a (simple undirected) graph <span class="math-container">$G$</span> is a function <span class="math-container">$f:V(G)\to\mathbb{N}$</span> such that <span class="math-container">$f(u)\neq f(v)$</span> whenever <span class="math-container">$u$</span> and <span class="math-container">$v$</span> have a common neighbour (i.e., <span class="math-container">$N(u)\cap N(v)\neq \emptyset$</span>).</p>
<p>The closest I  could find in the literature is strong subcoloring introduced in [1]. A strong subcoloring of <span class="math-container">$G$</span> is a function <span class="math-container">$f:V(G)\to\mathbb{N}$</span> such that <span class="math-container">$f(u)\neq f(v)$</span> whenever <span class="math-container">$d(u,v)=2$</span> (i.e. distance between <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$G$</span> is two). The difference between the two notions is that special labelling does not allow two adjacent vertices to have the same label if they have a common neighbour. Both notions are the same for triangle-free graphs.</p>
<p><strong>Reference</strong><br />
[1] <em>Shalu, M. A.; Vijayakumar, S.; Yamini, S. Devi; Sandhya, T. P.</em>, <a href="http://dx.doi.org/10.1007/s10878-018-0272-z" rel="nofollow noreferrer"><strong>On the algorithmic aspects of strong subcoloring</strong></a>, J. Comb. Optim. 35, No. 4, 1312-1329 (2018). <a href="https://zbmath.org/?q=an:1400.90266" rel="nofollow noreferrer">ZBL1400.90266</a>.</p>

<graph-theory><graph-colouring>
Graph labelling where vertices with a common neighbour get different labels
Cyriac Antony
# Graph labelling where vertices with a common neighbour get different labels

(Asked by: username_0 on 2021-03-20)

**Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?**  
A special labelling of a (simple undirected) graph $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $u$ and $v$ have a common neighbour (i.e., $N(u)\cap N(v)\neq \emptyset$).

The closest I could find in the literature is strong subcoloring introduced in [1]. A strong subcoloring of $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $d(u,v)=2$ (i.e. distance between $u$ and $v$ in $G$ is two). The difference between the two notions is that special labelling does not allow two adjacent vertices to have the same label if they have a common neighbour. Both notions are the same for triangle-free graphs.

**Reference**  
[1] *Shalu, M. A.; Vijayakumar, S.; Yamini, S. Devi; Sandhya, T. P.*, [**On the algorithmic aspects of strong subcoloring**](http://dx.doi.org/10.1007/s10878-018-0272-z), J. Comb. Optim. 35, No. 4, 1312-1329 (2018). [ZBL1400.90266](https://zbmath.org/?q=an:1400.90266).

**Tags:** graph-theory, graph-colouring


---

## 2 answers

### Answer by username_0 on 2021-04-02. Score: 3 | Accepted answer

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name *injective coloring*.

> An injective colouring of a graph $G$ is a colouring $c$ of the vertices
> of $G$ that assigns different colours to any pair of vertices that have a
> common neighbour.

There are a number of papers on injective coloring. The main graph classes studied are planar graphs [1,2,3], chordal graphs [4], regular graphs [5], and sparse graphs [6]

## References

[1] *Bu, Yuehua; Qi, Chentao; Zhu, Junlei; Xu, Ting*, [**Injective coloring of planar graphs**](http://dx.doi.org/10.1016/j.tcs.2021.01.007), [ZBL07300884](https://zbmath.org/?q=an:07300884).

[2] *Lužar, Borut; Škrekovski, Riste; Tancer, Martin*, [**Injective colorings of planar graphs with few colors**](http://dx.doi.org/10.1016/j.disc.2008.04.005), Discrete Math. 309, No. 18, 5636-5649 (2009). [ZBL1209.05093](https://zbmath.org/?q=an:1209.05093).

[3] *Bu, Yuehua; Wang, Chao; Yang, Sheng*, List injective coloring of planar graphs., [ZBL06986943](https://zbmath.org/?q=an:06986943).

[4] *Hell, Pavol; Raspaud, André; Stacho, Juraj*, [**On injective colourings of chordal graphs**](http://dx.doi.org/10.1007/978-3-540-78773-0_45), Laber, Eduardo Sany (ed.) et al., LATIN 2008 Berlin: Springer (ISBN 978-3-540-78772-3/pbk). LNCS 4957, 520-530 (2008). [ZBL1136.68463](https://zbmath.org/?q=an:1136.68463).

[5] *Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique*, [**On the injective chromatic number of graphs**](http://dx.doi.org/10.1016/S0012-365X(01)00466-6), Discrete Math. 256, No. 1-2, 179-192 (2002). [ZBL1007.05046](https://zbmath.org/?q=an:1007.05046).

[6] *Cranston, Daniel W.; Kim, Seog-Jin; Yu, Gexin*, [**Injective colorings of sparse graphs**](http://dx.doi.org/10.1016/j.disc.2010.07.003), Discrete Math. 310, No. 21, 2965-2973 (2010). [ZBL1209.05075](https://zbmath.org/?q=an:1209.05075).


---

### Answer by username_1 on 2021-03-21. Score: 2

$L(p,q)$ coloring is a function V $\rightarrow \mathbb{N}$ such that the labels on vertices at distance 1 differ by at least $p$ and vertices at distance 2 differ by at least $q$. Special labelling looks like $L(0,1)$ coloring.

> **Comments:**
> **username_0**: Are you aware of any paper that give non-trivial resuts on $L(0,1)$-coloring?  

---

