# Graph labelling where vertices with a common neighbour get different labels

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 . 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
 Shalu, M. A.; Vijayakumar, S.; Yamini, S. Devi; Sandhya, T. P., On the algorithmic aspects of strong subcoloring, J. Comb. Optim. 35, No. 4, 1312-1329 (2018). ZBL1400.90266.

## 2 Answers

`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 , regular graphs , and sparse graphs 

## References

 Bu, Yuehua; Qi, Chentao; Zhu, Junlei; Xu, Ting, Injective coloring of planar graphs, ZBL07300884.

 Lužar, Borut; Škrekovski, Riste; Tancer, Martin, Injective colorings of planar graphs with few colors, Discrete Math. 309, No. 18, 5636-5649 (2009). ZBL1209.05093.

 Bu, Yuehua; Wang, Chao; Yang, Sheng, List injective coloring of planar graphs., ZBL06986943.

 Hell, Pavol; Raspaud, André; Stacho, Juraj, On injective colourings of chordal graphs, Laber, Eduardo Sany (ed.) et al., LATIN 2008 Berlin: Springer (ISBN 978-3-540-78772-3/pbk). LNCS 4957, 520-530 (2008). ZBL1136.68463.

 Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique, On the injective chromatic number of graphs, Discrete Math. 256, No. 1-2, 179-192 (2002). ZBL1007.05046.

 Cranston, Daniel W.; Kim, Seog-Jin; Yu, Gexin, Injective colorings of sparse graphs, Discrete Math. 310, No. 21, 2965-2973 (2010). ZBL1209.05075.

$$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.

• Are you aware of any paper that give non-trivial resuts on $L(0,1)$-coloring? – Cyriac Antony Mar 22 at 8:42