zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Fixed-parameter complexity of $\lambda$-labelings. (English) Zbl 0982.05085
A $\lambda (p,q)$ labelling of a graph $G=(V,E)$ is an assignment of non-negative integers to the vertices in $V$, such that adjacent vertices get labels that differ by at least $p$, and vertices of distance two in $G$ get labels that differ by at least $q$. $L(G;p,q)$ is the minimum possible maximum value in a $\lambda (p,q)$ labelling of $G$. The standard $\lambda$-coloring problem is to determine $L(G;2,1)$ of a graph. This paper shows that this problem is solvable in polynomial time on almost $k$-trees (graphs that can be formed by adding $k$ edges to a tree), and is NP-hard for every fixed maximum label value. It is also shown for all values $p>q\geq 1$ that there are several $\lambda$ such that deciding if $L(G;p,q) \leq \lambda$ is NP-complete (taking $\lambda$ here as fixed part of the problem description). Some other related results are also shown.

MSC:
05C78Graph labelling
68R10Graph theory in connection with computer science (including graph drawing)
05C90Applications of graph theory
05C15Coloring of graphs and hypergraphs
WorldCat.org
Full Text: DOI
References:
[1] Abello, J.; Fellows, M. R.; Stillwell, J. C.: On the complexity and combinatorics of covering finite complexes. Australas. J. Combin. 4, 103-112 (1991) · Zbl 0763.05035
[2] R. Battiti, A.A. Bertossi, M.A. Bonuccelli, Assigning codes in wireless networks: bounds and scaling properties, manuscript, 1998.
[3] A. Brandstädt, Special graph classes -- a survey, Schriftenreihe des Fachsbereichs Mathematik, SM-DU-199, Universität Duisburg Gesamthochschule, 1991.
[4] Chang, G. J.; Kuo, D.: The $L(2,1)$-labeling problem on graphs. SIAM J. Discrete math. 9, 309-316 (1996) · Zbl 0860.05064
[5] Downey, R. G.; Fellows, M. R.: Parameterized complexity. Monographs in computer science (1998) · Zbl 0914.68076
[6] D. Fotakis, G. Pantziou, G. Pentaris, P. Spirakis, Frequency assignment in mobile and radio networks, manuscript, 1998. · Zbl 0929.68005
[7] Georges, J. P.; Mauro, D. W.: On the size of graphs labeled with a condition at distance two. J. graph theory 22, 47-57 (1996) · Zbl 0848.05056
[8] Georges, J. P.; Mauro, D. W.; Whittlesey, M. A.: Relating path coverings to vertex labellings with a condition at distance two. Discrete math. 135, 103-111 (1994) · Zbl 0811.05058
[9] Giaro, K.: The complexity of consecutive ${\Delta}$-labeling of bipartite graphs: 4 is easy, 5 is hard. Ars combin. 47, 287-298 (1997) · Zbl 0933.05050
[10] Griggs, J. R.; Yeh, R. K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete math. 5, 586-595 (1992) · Zbl 0767.05080
[11] J. van den, Heuvel, R.A. Leese, M.A. Shepherd, Graph labeling and radio channel assignment, http://www.maths.ox.ac.uk/users/gowerr/preprints.html, 1996. · Zbl 0930.05087
[12] K. Jonas, Graph colorings analogues with a condition at distance two: L(2,1)-labelings and list {$\lambda$}-labelings, Ph.D. Thesis, University of South Carolina, 1993.
[13] Kratochvı\acute{}l, J.: Regular codes in regular graphs are difficult. Discrete math. 133, 191-205 (1994) · Zbl 0821.68096
[14] Kratochvı\acute{}l, J.; Proskurowski, A.; Telle, J. A.: Covering regular graphs. J. combin. Theory ser. B 71, 1-16 (1997) · Zbl 0895.05049
[15] J. Kratochvı\acute{}l, A. Proskurowski, J.A. Telle, Covering directed multigraphs I. colored directed multigraphs. In: Graph-Theoretical Concepts in Computer Science, Proceedings of the 23rd WG ’97, Berlin, Lecture Notes in Computer Science, Vol. 1335, Springer, Berlin, 1997, pp. 242--257. · Zbl 0890.68095
[16] Kratochvı\acute{}l, J.; Proskurowski, A.; Telle, J. A.: Complexity of graph covering problems. Nord. J. Comput. 5, 173-195 (1998) · Zbl 0911.68076
[17] Van Leeuwen, J.: Graph algorithms. Handbook of theoretical computer science, A: algorithms and complexity, 527-631 (1990) · Zbl 0900.68258
[18] Lin, Y. -L.; Skiena, S. S.: Algorithms for square roots of graphs. SIAM J. Discrete math. 8, 99-118 (1995) · Zbl 0821.05052
[19] Liu, D. D. -F.; Yeh, R. K.: On distance two labellings of graphs. Ars combin. 47, 13-22 (1997) · Zbl 0933.05139
[20] Sakai, D.: Labeling chordal graphs: distance two condition. SIAM J. Discrete math. 7, 133-140 (1994) · Zbl 0794.05118
[21] Whittlesey, M. A.; Georgess, J. P.; Mauro, D. W.: On the lambda-coloring of qn and related graphs. SIAM J. Discrete math. 8, 499-506 (1995) · Zbl 0844.05084
[22] K.-C. Yeh, Labeling graphs with a condition at distance two, Ph.D. Thesis, University of South Carolina, 1990.