Optimal frequency assignment and planar list \(L(2, 1)\)-labeling
type: Item
instance of: scholarly article
title: Optimal frequency assignment and planar list \(L(2, 1)\)-labeling
zbMATH Open document ID: 1506.05185
author: Yanyan Li
published in: Journal of Combinatorial Optimization
publication date: 2022-10-18T00:00:00Z
review text: The \(L(2, 1)\) labeling problem is well known in frequency assignment tasks aiming to avoid interference. \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, No. 4, 586--595 (1992; Zbl 0767.05080)] conjectured that for a graph \(G\), with maximum degree \(k\), the minimum span of the \(L(2, 1)\) labeling is at most \(k^2\). The authors successfully establish that for a planar graph with maximum degree \(k\) of at least 5, and girth of at least 13, the minimum span of the \(L(2, 1)\) labeling is at most \(k+3\) and it is a tight upper bound.
reviewed by: V. Yegnanarayanan
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7603291
zbMATH Keywords: list \(L(2, 1)\)-labeling number
MaRDI profile type: Publication
full work available at URL: s10878-021-00791-5
OpenAlex ID: W3189764831
cites work: Combinatorial Nullstellensatz
cites work: Labeling planar graphs with a condition at distance two
cites work: The $L(2,1)$-Labeling Problem on Graphs
cites work: Coloring squares of planar graphs with girth six
cites work: Generalized list \(T\)-colorings of cycles
cites work: On the \(L(p,1)\)-labelling of graphs
cites work: Labelling Graphs with a Condition at Distance 2
cites work: Griggs and Yeh's conjecture and \(L(p,1)\)-labelings
cites work: Neighbor sum distinguishing index of subcubic graphs
cites work: A Theorem about the Channel Assignment Problem
cites work: A bound on the chromatic number of the square of a planar graph
cites work: Coloring the square of a planar graph
cites work: The \(L(2,1)\)-labelling of trees
cites work: Labelling planar graphs without 4-cycles with a condition on distance two
cites work: Labeling Planar Graphs with Conditions on Girth and Distance Two
cites work: Labeling planar graphs without 4,5-cycles with a condition on distance two
cites work: The \(L(p, q)\)-labelling of planar graphs without 4-cycles
cites work: The List \(L(2, 1)\)-labeling of planar graphs
cites work: List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
cites work: Optimal channel assignment and \(L(p,1)\)-labeling
cites work: The list \(L(2,1)\)-labeling of planar graphs with large girth
DOI: 10.1007/S10878-021-00791-5
description: scientific article; zbMATH DE number 7603291