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.

[1] 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.


`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]


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

[2] 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.

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

[4] 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.

[5] 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.

[6] 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.