L(2,1)-coloring

File:L(2,1)-coloring of C6.svg

L(2, 1)-coloring or L(2,1)-labeling is a particular case of L(h, k)-coloring. In an L(2, 1)-coloring of a graph, G, the vertices of G are assigned color numbers in such a way that adjacent vertices get labels that differ by at least two, and the vertices that are at a distance of two from each other get labels that differ by at least one.{{cite book |last1=Chartrand |first1=Gary |last2=Zhang |first2=Ping|author2-link=Ping Zhang (graph theorist) |authorlink1=Gary Chartrand |title=Chromatic Graph Theory |year=2009 |publisher=CRC Press |chapter=14. Colorings, Distance, and Domination |pages=397–438}}

An L(2,1)-coloring is a proper coloring, since adjacent vertices are assigned distinct colors. However, rather than counting the number of distinct colors used in an L(2,1)-coloring, research has centered on the L(2,1)-labeling number, the smallest integer $n$ such that a given graph has an L(2,1)-coloring using color numbers from 0 to $n$. The L(2,1)-coloring problem was introduced in 1992 by Jerrold Griggs and Roger Yeh, motivated by channel allocation schemes for radio communication. They proved that for cycles, such as the 6-cycle shown, the L(2,1)-labeling number is four, and that for graphs of degree$\backslash Delta$ it is at most $\backslash Delta^2+2\backslash Delta$.{{cite journal

| last1 = Griggs | first1 = Jerrold R.

| last2 = Yeh | first2 = Roger K.

| doi = 10.1137/0405048

| issue = 4

| journal = SIAM Journal on Discrete Mathematics

| mr = 1186826

| pages = 586–595

| title = Labelling graphs with a condition at distance 2

| volume = 5

| year = 1992}}