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://fap.zib.de/index.php

http://rkyeh.math.fcu.edu.tw/Articles.htm

http://www.math.uiuc.edu/~west/openp/L21.html

http://www.math.uiuc.edu/~j-kang5/L21.html

http://wfap.di.uniroma1.it

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. 1344-1371, 2011.

List of comments

o

09/10/2021

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.)

o

06/22/2021

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

o

10/3/2015

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).

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 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.

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), 646-660

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), 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.

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. 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

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 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.

x

5/11/2009

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.

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 Systems-II: Express Briefs, vol. 55, no. 1, pp. 70-73, 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), 1217-1231

x

07/18/2006

D. Sakai Troxell

you might want to update this reference (it used to be cited as a DIMACS Tech. Report):

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

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:

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:

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 R-unit 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 k-Coloring 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 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.

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, 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.

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 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 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: 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.

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 Lambda-Colorings of Graphs. The Computer Journals, 47 (2004), 193-204.

x

10/20/2004

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

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) (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.

x

09/30/2004

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.