The L(h,k)Labelling Problem 

In this page you can find a survey and annotated bibliography on the L(h,k)labelling problem. A continuously updated catalog of results on the L(h,k)labelling problem follows. If you happen to notice some missing results, errors, not updated references, please write to calamo AT di DOT uniroma1 DOT it.

some interesting links 
http://rkyeh.math.fcu.edu.tw/Articles.htm http://www.math.uiuc.edu/~west/openp/L21.html http://www.math.uiuc.edu/~jkang5/L21.html http://kam.mff.cuni.cz/conferences/WFAP07/


Survey and Annotated Bibliography:
(vers. October, 2014)
Updated Survey and Annotated Bibliography: The Computer Journal, 54(8), pp. 13441371, 2011. PLEASE, CITE THIS NEW VERSION OF THE SURVEY.Survey and Annotated Bibliography: The Computer Journal, 49(5), pp. 585608, 2006. 
List of comments 

(o: not included in the paper yet; x: already included in the paper)  
o 
10/3/2015 
Tomas Masarik 
I managed to prove that the problem of L(2,1)edge labeling is NPcomplete if \lambda³5 and polynomial if \lambda²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 postproceedings. I'll let you know when it will be published. Now we have a version on arXiv: (http://arxiv.org/abs/1508.01014). 
o 
09/23/2015 
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 listcoloring or online listcoloring, sometimes called paintability. (A few are socalled 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 (? + 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 ? >= C the graph G^2 is (? + 2)Choosable. Listcoloring Squares of Planar Graphs without 4cycles and 5cycles. Daniel W. Cranston and Bobby Jaeger. (15pp). Let G be a planar graph with no 4cycle and no 5cycle (although 3cycles are allowed). We show that if ? >= 32, then G^2 is (? + 3)Choosable. Listcoloring the Square of a Subcubic Graph. Daniel W. Cranston and SeogJin Kim. Journal of Graph Theory. Vol. 57, January 2008, pp. 6587. We show that if G is a connected graph with ? = 3 and G is not the Petersen graph, then G^2 is 8choosable. Painting Squares in ?^21 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 (?^21)paintable (this is a stronger version of choosable). Sufficient sparseness conditions for G^2 to be (?+1)choosable, when ? ³ 5. Daniel W. Cranston and Riste Skrekovski. Discrete Applied Math. Vol. 162(10), January 2014, pp. 167176. 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. 8697. Injective Colorings of Graphs with Low Average Degree. Daniel W. Cranston, SeogJin Kim, and Gexin Yu. Algorithmica. Vol. 60(3), July 2011, pp. 553568. Injective Colorings of Sparse Graphs. Daniel W. Cranston, SeogJin Kim, and Gexin Yu. Discrete Math. Vol. 310, no. 21, 6 November 2010, pp. 29652973. 
x 
09/27/2013 
Clement 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), 646660 
x 
11/24/2011 
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), 13721381. 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), 15591569. Z. Dvorak, D. Kral, P. Nejedly, R. Skrekovski: Distance constrained labelings of planar graphs with no short cycles, Discrete Applied Mathematics 157 (2009), 26342645. R. Babilon, V. Jelinek, D. Kral, P. Valtr: Labelings of graphs with fixed and variable edgeweights, SIAM Journal on Discrete Mathematics 21 (2007), 688706. P. Bella, D. Kral, B. Mohar, K. Quittnerova: Labeling planar graphs with a condition at distance two, European Journal of Combinatorics 28 (2007), 22012239. 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), 536543. 
x 
11/24/2011 
Denise Troxell 
Here are the links to our latest publications on the subject: http://www.sciencedirect.com/science/article/pii/S0166218X11003969 http://www.sciencedirect.com/science/article/pii/S0893965911000097 
x 
9/30/2011 
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. 
x 
4/28/2011 
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. JunoszaSzaniawski, 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 
x 
1/18/2010 
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 sumup, 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. 
x 
5/11/2009 
S. Noble 
I thought you might be interested in a preprint of mine: Eggemann, N., Havet, F., Noble, S.D. kL(2,1)Labelling for Planar Graphs is NPcomplete for k >= 4 available at http://people.brunel.ac.uk/~mastsdn/L21NPshort.pdf for your annotated bibliography. As the title suggests we show that L(2,1)labelling with span at most k is NPcomplete 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. 
x 
May 2009 
B. Sinaimeri 
It appeared on SODA '08 a paper by Havet, Reed and Sereni proving the Griggs and Yeh's conjecture. 
x 
6/16/2008 
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 SystemsII: Express Briefs, vol. 55, no. 1, pp. 7073, Jan. 2008. 
x 
4/16/2008 
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. 
x 
10/16/2006 
R.K. Yeh 
a survey article of mine has been published ib Discrete Math. 306 (2006), 12171231 
x 
07/18/2006 
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) 15221540. 
x 
07/18/2006 
H. Balakrishnan 
There is a LaTeX mistake in the Nordhaus and Gaddum bounds for L(2,1) labelling. 
x 
07/18/2006 
S. Klavzar 
Reference [76] has appeared as The \Delta2conjecture for L(2,1)labelings is true for direct and strong products of graphs, IEEE Trans. Circuits and Systems II 53 (2006) 274277. 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) 257265. 
x 
07/18/2006 
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) 11011107. "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 uptodate. 
x 
12/13/2005 
G. Agnarsson 
The papers of mine that might be relevant to the topic of L(h,k) labellings are as follows: (1) Geir Agnarsson; Magnus M. Halldorsson: Coloring powers of planar graphs, SIAM Journal of Discrete Mathematics, 16 (2003), No.~4, 651  662. (2) Geir Agnarsson; Magnus M. Halldorsson: On Colorings of Squares of Outerplanar Graphs, Proceedings of the Fifteenth Annual ACMSIAM Symposium On Discrete Algorithms, New Orleans, LA, 2004, 237246, (2004). (3) 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 
x 
10/27/2005 
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. 
x 
5/27/2005 
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. 
x 
5/6/2005 
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 Runit sphere graphs and L(2,1)labelings. 
x 
2/4/2005 
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 kColoring in LinMSOL. 
x 
1/17/2005 
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: . 
x 
11/10/20 04 
G. Fertin 
I am afraid there might be some intersection between sections 3.2 and 3.3. Indeed, any ddimensional grid is a cartesian of d paths, and any ddimensional 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. 
o 
11/23/20 04 
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, 525, 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.116. 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. Graphtheoretic concepts in computer science, 131142, 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 cliquewidth. Graphtheoretic concepts in computer science, 370382, 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 (13), (2004), pp. 261292. 
x 
11/9/20 04 
V.G. Papadopoulou 
 Section 2. L(1,1)labeling: you can add also reference [AFNPS02] where we provide a new local NPcompleteness 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 NPcompleteness 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 lth 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 NPcompleteness proof [42] but the simpler one of [TCS03] prove the NPcompleteness 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 hiarchically 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: NPCompleteness 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: PSPACEcompleteness and Approximations". Mathematical Foundations of Computer Science, August 2002 (MFCS 2002), LNCS 2420, pp. 8192. [FNPS02] D. Fotakis, S. Nikoletseas, V. Papadopoulou and P. Spirakis: "Radiocolorings in Periodic Planar Graphs: PSPACECompleteness 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: PSPACECompleteness and Efficient Approximations for the Optimal Number of Frequencies". 1st International Conference "From Scientific Computing to Computational Engineering", MiniSymposium Computational Mathematics & Applications. 810, 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), 110. 
x 
10/26/2004 
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 LambdaColorings of Graphs. The Computer Journals, 47 (2004), 193204. 
x 
10/20/2004 
M. Salavatipour 
the
journal version of our paper (that had appeared 
x 
10/19/2004 
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. 
x 
10/19/2004 
J. Kratochvil 
If
a graph has bounded max degree then the L(2,1) 
x 
09/30/2004 
J. Fiala 
if
I am not mistaken  for fixed span l the L(p_1,...,p_k)
labeling can
