In this page, you can find a survey and annotated bibliography on the L(h,k)-labeling problem.
A continuously updated catalog of results on the L(h,k)-labeling problem follows. If you happen to notice some missing results, errors, or not updated references, please write to calamo AT di DOT uniroma1 DOT it. It has been a while since I last updated the Survey, but I will publish your comment here very soon.
Survey and Annotated Bibliography: (vers. October, 2014)
Updated Survey and Annotated Bibliography: The Computer Journal, 54(8), pp. 1344-1371, 2011.
PLEASE, CITE THIS NEW VERSION OF THE SURVEY.
Survey and Annotated Bibliography: The Computer Journal, 49(5), pp. 585-608, 2006.
blue text: not incorporated yet - green text: incorporated in the Survey
May 2025 from Steven Noble:
have not thought about L(2,1) for many years, but by chance I was led to look at your online survey article. You mention that L(2,1) is open for outerplanar graphs. This was resolved by my PhD student Angela Koller in her thesis, where she gave a polynomial time algorithm, albeit with a huge exponent. The full citation is
Angela Koller. "The Frequency Assignment Problem" PhD Thesis, Brunel University (2005).
September 2021 from Mehmet Akif YETIM:
For a possible contribution to your web page "The L(h,k)-labelling Problem", I mention my paper "L(p,q)-labeling of graphs with interval representations" (which is accepted for publication in the journal Discusssiones Mathematicae Graph Theory - https://doi.org/10.7151/dmgt.2426.)
June 2021 from Konstanty Szaniawski:
There is a mistake in Theorem 6 of the paper "On the L(h, k )-Labeling of Co-Comparability Graphs and Circular-Arc Graphs" in NETWORKS 2009.
Nevertheless, the result for interval graphs was improved in: https://arxiv.org/abs/1909.05425
Moreover, here some other related papers are: https://www.sciencedirect.com/science/article/abs/pii/S0166218X19303932?via%3Dihub https://arxiv.org/abs/1802.09503
October 2015 from Tomas Masarik:
I managed to prove that the problem of L(2,1)-edge labeling is NP-complete if lambda is greater than or equal to 5 and polynomial if lambda is less than or equal to 4.
I'm going to present it on IWOCA (http://iwoca2015.di.univr.it/) conference in Verona. After the conference it will be published as post-proceedings. I'll let you know when it will be published. Now we have a version on arXiv: (http://arxiv.org/abs/1508.01014).
September 2015 from Dan Cranston:
I'm writing to mention some of my papers that might be relevant. Most of these results fit into the case of L(1,1)-labeling, although many of them are actually for list-coloring or online list-coloring, sometimes called paintability. (A few are so-called injective coloring, which is L(0,1)-labeling.) You can download a preprint of each paper either at http://www.people.vcu.edu/~dcranston/pubs/ or at http://arxiv.org/a/cranston_d_1.html
Planar Graphs of Girth at least Five are Square (Delta + 2)-Choosable. Marthe Bonamy, Daniel W. Cranston, and Luke Postle. (18pp) We prove a conjecture of Dvorak et al. that there exists a constant C such that for every planar graph with girth at least 5 and Delta >= C the graph G^2 is (Delta + 2)-Choosable.
List-coloring Squares of Planar Graphs without 4-cycles and 5-cycles. Daniel W. Cranston and Bobby Jaeger. (15pp). Let G be a planar graph with no 4-cycle and no 5-cycle (although 3-cycles are allowed). We show that if Delta >= 32, then G^2 is (Delta + 3)-Choosable.
List-coloring the Square of a Subcubic Graph. Daniel W. Cranston and Seog-Jin Kim. Journal of Graph Theory. Vol. 57, January 2008, pp. 65-87. We show that if G is a connected graph with Delta = 3 and G is not the Petersen graph, then G^2 is 8-choosable.
Painting Squares in ?^2-1 Shades. Daniel W. Cranston and Landon Rabern. Submitted. (23pp) We generalize paper #3. We show that if G is a connected graph with maximum degree ? and G is not a Moore graph, then G is (Delta^2-1)-paintable (this is a stronger version of choosable).
Sufficient sparseness conditions for G^2 to be (?+1)-choosable, when Delta >= 5. Daniel W. Cranston and Riste Skrekovski. Discrete Applied Math. Vol. 162(10), January 2014, pp. 167-176.
Choosability of the square of a planar graph with maximum degree four. Daniel W. Cranston, Rok Erman, and Riste Skrekovski. Australasian Journal of Combinatorics. Vol 59(1), June 2014, pp. 86-97.
Injective Colorings of Graphs with Low Average Degree. Daniel W. Cranston, Seog-Jin Kim, and Gexin Yu. Algorithmica. Vol. 60(3), July 2011, pp. 553-568.
Injective Colorings of Sparse Graphs. Daniel W. Cranston, Seog-Jin Kim, and Gexin Yu. Discrete Math. Vol. 310, no. 21, 6 November 2010, pp. 2965-2973.
September 2013 fromClement Charpentier:
I might have noticed some incoherences and i'd like to ask about it.
About planar graphs, in section 4.6, page 18, you say Jonas proved in his P.h.D that " L{1,1}(G) is at most 8 x Delta - 21 " This seems wrong for me in the case Delta = 3, where we know L{1,1} is at least 6. I couldn't obtain access for this thesis however.
In the end of the same paragraph, you relate this result : " L{1,1}(G) is at most 5 x Delta " And you precise this is better than the better asymptotic bound when Delta is at most 24. However, you give reference before to a bound of 3 x Delta + 5, which is better than 5 x Delta in each case.
Also i published a paper you might fight interesting. We give a bound for L{p,q} of graphs with bounded maximum average degree, which improve the known bounds on L{p,q} for planar graphs with girth 5, 6 and 7.
Clement Charpentier, Mickael Montassier, Andre Raspaud : L(p,q)-labeling of sparse graphs, Journal of Combinatorial Optimization 25:4 (2013), 646-660
November 2011 from Daniel Kral:
I am enclosing the list of the paper that I have published in the area in the last few years in case you might not be aware of them.
R. Erman, S. Jurecic, D. Kra, K. Stopar, N. Stopar: Optimal real number graph labelings of a subfamily of Kneser graphs, SIAM Journal on Discrete Mathematics 23 (2009), 1372-1381.
D. Kral, P. Skoda: Bounds for the real number graph labellings and application to labellings of the triangular lattice, SIAM Journal on Discrete Mathematics 22 (2008), 1559-1569.
Z. Dvorak, D. Kral, P. Nejedly, R. Skrekovski: Distance constrained labelings of planar graphs with no short cycles, Discrete Applied Mathematics 157 (2009), 2634-2645.
R. Babilon, V. Jelinek, D. Kral, P. Valtr: Labelings of graphs with fixed and variable edge-weights, SIAM Journal on Discrete Mathematics 21 (2007), 688-706.
P. Bella, D. Kral, B. Mohar, K. Quittnerova: Labeling planar graphs with a condition at distance two, European Journal of Combinatorics 28 (2007), 2201-2239.
D. Kral, R. Skrekovski, M. Tancer: Construction of large graphs with no optimal surjective L(2,1)-labelings, SIAM Journal on Discrete Mathematics 20 (2006), 536-543.
November 2011 from Denise Troxell:
Here are the links to our latest publications on the subject:
September 2011 from Martin Kupec:
I have written a master thesis on the topic of complexity of L(h,k)-labelling. The thesis was advised my Jiri Fiala. You might be interested in it.
April 2011 from Pawel Rzazewski:
Concerning the exact algorithms for L(2,1)-labeling, mentioned in your survey, the result 3.23 was not published in the paper you refer to, but in the following: K. Junosza-Szaniawski, P. Rz??ewski, On the Complexity of Exact Algorithm for L(2,1)-labeling of Graphs, to appear in Information Processing Letters, preliminary version in KAM Series 2010, 992
January 2010 from J.-S. Sereni:
In the journal version of our SODA 08 paper (currently under review), we adapted the proof to obtain the same bounds for L(p,1)-labellings (and not only L(2,1)). [A link to the preprint is: http://iti.mff.cuni.cz/series/files/iti454.pdf ] To sum-up, the results we obtain are the following [where our definition of lambda(p,1) differs by 1 with the one of Griggs adn Yeh, which explains why we have Delta^2+1 and not Delta^2]. Theorem: For any fixed integer p, there exists a constant Cp such that for every integer Delta and every graph G of maximum degree Delta, lambda(p,1)(G) <= Delta^2 + Cp. This theorem is obtained as a corollary of the following. Theorem: For any fixed integer p, there is a Delta_p such that for every graph G of maximum degree Delta >= Delta_p, lambda(p,1)(G) <= Delta^2 + 1.
May 2009 from S. Noble:
I thought you might be interested in a preprint of mine: Eggemann, N., Havet, F., Noble, S.D. k-L(2,1)-Labelling for Planar Graphs is NP-complete for k >= 4 available at http://people.brunel.ac.uk/~mastsdn/L21NP-short.pdf for your annotated bibliography. As the title suggests we show that L(2,1)-labelling with span at most k is NP-complete for planar graphs for every constant k>=4. This is best possible and was only previously known for even values of k >= 8.
In your bibliography you mention that it is known for all values of k but the paper you cite [62], doesn't show this. The relevant theorem only explicitly deals with the case when k is part of the input, although it clearly establishes the theorem for a constant k = 8. There is a similarly titled conference paper by the same authors where they give a different proof (for k part of the input) from which it might be possible to establish the result for all large constant k, but the precise position is far from clear.
May 2009 from B. Sinaimeri:
It appeared on SODA '08 a paper by Havet, Reed and Sereni proving the Griggs and Yeh's conjecture.
June 2008 from P.K. Jha:
In case you didn't know, here is a paper jointly written by me: M.E. Haque and P.K. Jha, L(j,k)-labelings of Kronecker products of complete graphs, IEEE Trans. Circuits and Systems-II: Express Briefs, vol. 55, no. 1, pp. 70-73, Jan. 2008.
April 2008 from J. Fiala:
(speaking about paper: Jiri Fiala, Petr Golovach and Jan Kratochvil "Computational complexity of the distance constrained labeling problem for trees" accepted to ICALP '08) We've solved the problem we worked on last 5 years.
October 2006 from R.K. Yeh:
a survey article of mine has been published ib Discrete Math. 306 (2006), 1217-1231
July 2006 from D. Sakai Troxell:
you might want to update this reference (it used to be cited as a DIMACS Tech. Report):
"L(2,1)-labelings of the Cartesian product of two cycles," Schwarz, C., and Troxell, D.S., Discrete Applied Math. 154 (2006) 1522--1540.
July 2006 from H. Balakrishnan:
There is a LaTeX mistake in the Nordhaus and Gaddum bounds for L(2,1) labelling.
July 2006 from S. Klavzar:
Reference [76] has appeared as
The \Delta2-conjecture for L(2,1)-labelings is true for direct and strong products of graphs, IEEE Trans. Circuits and Systems II 53 (2006) 274-277.
and reference [78] as
Optimal L(d,1)-labelings of certain direct products of cycles and Cartesian products of cycles, Discrete Appl. Math. 152 (2005) 257-265.
July 2006 from D. Sakai Troxell:
Your survey is very helpful for the researchers in the area of distance labelings. As a matter of fact, we cite it in two of our recent papers:
An extension of the channel assignment problem: L(2,1)-labelings of Generalized Petersen graphs, Adams, S.S., Cass, J., Troxell, D.S.IEEE Transactions on Circuits and Systems I, 53 (2006) 1101-1107.
"The minimum span of L(2,1)-labelings of certain generalized Petersen graphs," Adams, S.S., Cass, J., Tesch, M., Troxell, D.S., Wheeland, C., submitted.
Thanks for maintaining your survey up-to-date.
December 2005 from G. Agnarsson:
The papers of mine that might be relevant to the topic of L(h,k) labellings are as follows:
Geir Agnarsson; Magnus M. Halldorsson: Coloring powers of planar graphs, SIAM Journal of Discrete Mathematics, 16 (2003), No.~4, 651 -- 662.
Geir Agnarsson; Magnus M. Halldorsson: On Colorings of Squares of Outerplanar Graphs, Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms, New Orleans, LA, 2004, 237--246, (2004).
Geir Agnarsson, Magnus M. Halldorsson, On colorings of squares of outerplanar graphs, Journal version of the above. Submitted, preprint available at: http://math.gmu.edu/~geir/somepapers.html
October 2005 from J. Griggs:
This is just to announce that my joint papers with Teresa Jin "Real number channel assignments for lattices" and "Real number labelings for paths and cycles" are now available on my homepage. They are now submitted. They follow our paper "Real number graph labelings with distance conditions" which has been accepted by SIDMA. The recently revised, final version, is now available on my homepage. We have another, shorter, paper in a rough draft stage, which we plan to complete and submit in the next few weeks. It will also be posted on the Web when ready.
May 2005 from G. Agnarsson:
Also, please be aware that there are some pesky mistakes in our SODA'04 version: For example, the outerplanar chordal graph F_6=Hat(Hat(K_3)) of Delta=6 has chromatic number 7 and not 8 as claimed. There are other mistakes as well...., We are sorry about this.
May 2005 from D. Troxell:
(speaking about the L(2,1)-labeling on interval graphs) (...)I only recall one paper years ago by Z.D. Shao (Nanjing University) that touched on the subject of R-unit sphere graphs and L(2,1)-labelings.
February 2005 from J. Fiala:
(...) The graph used in the reduction for L(2,1)-coloring and in the radio coloring paper is in fact a graph with exactly one prime graph in its modular decomposition tree. This is a P4 in the root of the tree. Hence the graph is obtained from a P4 by substituting cographs into the four vertices of the P4. The reasoning concerning LinMSOL does not work. Not even Coloring is in LinMSOL. You need to fix the parameter to have k-Coloring in LinMSOL.
January 2005 from X. T. Jin:
you can download two of my joint papers with Dr. Griggs in my homepage: www.math.sc.edu/~jin2/myself.html or in Dr. Griggs's homepage.
November 2004 from G. Fertin:
I am afraid there might be some intersection between sections 3.2 and 3.3. Indeed, any d-dimensional grid is a cartesian of d paths, and any d-dimensional torus is a cartesian product of cycles. Hence, separating the case grids/tori from the case cartesian product of paths/cycles might not be good.
November 2004 from F. Fomin:
There is a variation of L(h,k)-labeling with precoloring.(The paper [41] in the version on November 8) Golovach proved that L(2,1)-labeling with precoloring is NP complete on cacti. MR1948822 (2003j:05045) Golovach, P. A. Systems of pairs of $q$-distant representatives, and graph colorings. (Russian) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 293 (2002), Teor. Slozhn. Vychisl. 7, 5--25, 181. Variation on L(2,1) labeling with precoloring can be found also in H. L. Bodlaender, H. Broersma, F. V. Fomin, A. V. Pyatkin, and G. J. Woeginger, Radio labeling with preassigned frequencies, SIAM Journal on Optimization 15 (1), (2004), pp.1-16. BBC coloring is a natural generalization of L(2,1) coloring: MR2080075 Broersma, Hajo; Fomin, Fedor V.; Golovach, Petr A.; Woeginger, Gerhard J. Backbone colorings for networks. Graph-theoretic concepts in computer science, 131--142, Lecture Notes in Comput. Sci., 2880, Springer, Berlin, 2003. Graphs of bounded cliquewidth generalize graphs of bounded treewidth. There is a paper of Todinca: [2] MR2080095 Todinca, Ioan Coloring powers of graphs of bounded clique-width. Graph-theoretic concepts in computer science, 370--382, Lecture Notes in Comput. Sci., 2880, Springer, Berlin, 2003. Finally, ref [38] appeared in TCS , better reference now is J. Fiala, A. V. Fishkin, and F. V. Fomin, On distance constrained labeling of disk graphs, Theoretical Computer Science 326 (1-3), (2004), pp. 261-292.
November 2004 from V.G. Papadopoulou:
Section 2. L(1,1)-labeling: you can add also reference [AFNPS02] where we provide a new local NP-completeness proof for this problem on planar graphs.
Section 2. L(2,1)-labeling: you can add also reference [TCS03, not published yet, but accepted] where we provide a new local NP-completeness proof for this problem on planar graphs.
Section 3. Bounded treewidth graphs: I would like to mention that the solution of [11, your citations] actually solves a generalization of L(1,1)-labeling, the problem of coloring the l-th power of a graph G, G^l.
Section 3.6. Planar graphs: L(1,1)-labeling: Perhaps you could mention that the result of [88, your citations], applies here resulting to an 1,66 approximation algorithm.
same section L(2,1)-labelling. The NP-completeness proof [42] but the simpler one of [TCS03] prove the NP-completeness of the problem for planar graphs of any degree, closing the open problem of [11].
I would like to contact you another research line for L(1,1)-labelling done via the Probabilistic tools. In a work of our group [FNPS03] we provide an upper bound for the problem of for graphs of girth at most 7. A parallel work of [Alon02] provides improved upper bounds for the problem for graphs of girth g = 3; 4; 5 or 6, and g \geq 7. In particular, for the former case, they prove that they bound the optimal number of colors needed to color the square of a graph of girth g \geq 7 with \Theta(\Delta^2/lod \Delta).
Finally, I would like to contact you relevant research line, of the L(h, k) problem on networks specified by succinct models, including periodically or hierarchically specified networks, done by our group, [AFNPS02, FNPS02,FNPS04]. You can also visit my home page, in http://students.ceid.upatras.gr/~viki/
[TCS03] D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis: NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. Journal of Theoretical Computer Science (to appear).
[AFNPS02] M. Andreou, D. Fotakis, S. Nikoletseas, V. Papadopoulou and P. Spirakis: "On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-completeness and Approximations". Mathematical Foundations of Computer Science, August 2002 (MFCS 2002), LNCS 2420, pp. 81-92.
[FNPS02] D. Fotakis, S. Nikoletseas, V. Papadopoulou and P. Spirakis: "Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies". Workshop on Graph Theoretic Concepts 2002 (WG 2002).
[FNPS04] Fotakis D. A., Nikoletseas S. E., Papadopoulou V. G., Spyrakis P. G.: "Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Number of Frequencies". 1st International Conference "From Scientific Computing to Computational Engineering", Mini-Symposium Computational Mathematics & Applications. 8-10, Semp. 2004.
[FNPS03] S. Nikoletseas, V. Papadopoulou and P. Spirakis: "Radiocoloring Graphs via the Probabilistic Method". 4th Panhellenic Logic Symposium, 2003.
[Alon02] N. Alon and B. Mohar, The chromatic number of graph powers, Combinatorics, Probability and Computing 11 (2002), 1-10.
October 2004 from J. van Leeuwen:
the revised version of our STACS paper appeared in the Computer Journal. The revised version is the better reference now: H.L.Bodlaender, T. Kloks, R.B. Tan, E.J. van Leeuwen. Approximations for Lambda-Colorings of Graphs. The Computer Journals, 47 (2004), 193-204.
October 2004 from M. Salavatipour:
the journal version of our paper (that had appeared in ESA'02) is coming out soon. The title is "A Bound on the Chromatic Number of the Square of a Planar Graph". It has stronger results for L(p,q)-labeling for planar graphs than our conference version (almost by a factor of 2). You can download it from my webpage at www.cs.ualberta.ca/~mreza
October 2004 from R. Yeh:
I have done some survey work as well. The article has been send to Disc. Math. about a year ago. Referees' report came to me on May (or maybe June), but I did not do anything on that paper since I was full. However I have revised the article and sent back to DM last month. You covered some results that I did not and vice versa. Further several master students' (in Taiwan) theses are not included since I do not have a complete list.
October 2004 from J. Kratochvil:
If a graph has bounded max degree then the L(2,1) (and more generally L(h,k)) span is also bounded, and hence the question L(h,k)(G)\le lambda can be expressed in MSOL and therefore is polynomial for graphs of bounded treewidth.
September 2004 from J. Fiala:
if I am not mistaken - for fixed span l the L(p_1,...,p_k) labeling can be expressed in MSOL without quantifiers over the edge sets, so the decision problem whether L(p_1,...,p_k)(G) <= l can be decided in a polynomial time for graphs of bounded cliquewidth (by works of Coucelle and others), which includes also cographs.