On distance two labelling of unit interval graphs

Peter Che Bor Lam, Tao Ming Wang, Wai Chee SHIU, Guohua Gu

Research output: Contribution to journalJournal articlepeer-review


An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance at most two get different numbers and adjacent vertices get numbers which are at least two apart. The L(2, 1)-labelling number of G, denoted by λ(G), is the minimum range of labels over all such labellings. In this paper, we first discuss some necessary and sufficient conditions for unit interval graph G to have λ(G) = 2χ(G) - 2 and then characterize all unit interval graphs G of order no more than 3χ(G) - 1, where χ(G) is the chromatic number of G. Finally, we discuss some subgraphs of unit interval graphs G on more than 2χ(G) + 1 vertices with λ(G) = 2χ(G).

Original languageEnglish
Pages (from-to)1167-1179
Number of pages13
JournalTaiwanese Journal of Mathematics
Issue number4
Publication statusPublished - Aug 2009

Scopus Subject Areas

  • Mathematics(all)

User-Defined Keywords

  • L(2,1)-labelling
  • Unit interval graph


Dive into the research topics of 'On distance two labelling of unit interval graphs'. Together they form a unique fingerprint.

Cite this