The L(2,1)-Labeling Problem on Graphs

DOI10.1137/S0895480193245339zbMATH Open0860.05064OpenAlexW2085421834MaRDI QIDQ4881295FDOQ4881295

Authors:

Publication date: 21 April 1997

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480193245339

Recommendations

An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees
On $L(d,1)$-labelings of graphs
$L(2,1)$-labeling of interval graphs
An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees

zbMATH Keywords

labeling trees chordal graphs cographs polynomial time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (only showing first 100 items - show all)

The $L(2,1)$-labeling on Cartesian sum of graphs
New upper bounds on the $L(2,1)$-labeling of the skew and converse skew product graphs
On a labeling problem in graphs
On the $L(2, 1)$-labelling of block graphs
Some open problems on graph labelings
Improved self-stabilizing algorithms for $L(2, 1)$-labeling tree networks
Equitable colorings of bounded treewidth graphs
$L(2, 1)$-labeling of permutation and bipartite permutation graphs
The $L(2,1)$-labeling on the skew and converse skew products of graphs
(2,1)-total labelling of trees with sparse vertices of maximum degree
$L(p,q)$-labelling of $K_{4}$-minor free graphs
On critical trees labeled with a condition at distance two
Title not available (Why is that?)
Labeling trees with a condition at distance two
On $n$-fold $L(j,k)$-and circular $L(j,k)$-labelings of graphs
On the number of 2-packings in a connected graph
A sufficient condition for a tree to be $(\Delta+1)$-$(2,1)$-totally labelable
$\lambda$-coloring matrogenic graphs
A note on collections of graphs with non-surjective lambda labelings
A linear time algorithm for $L(2,1)$-labeling of trees
Extremal problems on consecutive $L(2,1)$-labelling
An extremal problem on non-full colorable graphs
The $L(d_1,d_2)$-labeling problem on graphs
$L(h,k)$-labelings of Hamming graphs
Labeling graphs with two distance constraints
On $\text{Ł}(\wp, \wp - 1, \dots, 1)$ labelings of circulant graphs
$k$-path partitions in trees
Hamiltonian path saturated graphs with small size
Distance-two labelings of digraphs
$L(2, 1)$-labeling of circulant graphs
Labelled (Hyper)Graphs, Negotiations and the Naming Problem
Algorithms for graphs with small octopus
Linear and cyclic distance-three labellings of trees
An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
$L(3,1)$-labeling of circulant graphs
Labelling planar graphs without 4-cycles with a condition on distance two
Distance constrained labelings of planar graphs with no short cycles
Distance-two labellings of Hamming graphs
A complete $L (2, 1)$ span characterization for small trees
Injective colorings with arithmetic constraints
Frequency assignment problem in networks with limited spectrum
Distance-two labelings of graphs
Title not available (Why is that?)
Recent progress in mathematics and engineering on optimal graph labellings with distance conditions
A note on the chromatic number of the square of Kneser graph $K(2 k + 1, k)$
$L(2, 1)$-labelling of graphs with few $P_4$'s
A new approach to the chromatic number of the square of Kneser graph $K(2k+1,k)$
On the $k$-path cover problem for cacti
Distance Constrained Labelings of Trees
$L(2,1)$-labeling of Kneser graphs and coloring squares of Kneser graphs
A lower bound technique for radio $k$-coloring
Distance two labelling and direct products of graphs
List version of $L(d,s)$-labelings
The path-partition problem in block graphs
On the $k$-path partition of graphs.
Title not available (Why is that?)
Irreducibility of L(2, 1)-coloring and Inh-Colorability of Some Classes of Graphs
$L(p,q)$-labeling and integer tension of a graph embedded on torus
List backbone colouring of graphs
Graph covers: where topology meets computer science, and simple means difficult
Title not available (Why is that?)
α2-labeling of graphs
Computing $L(p, 1)$-labeling with combined parameters
Distance Constrained Labelings of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-minor Free Graphs
Partial and perfect path covers of cographs
Optimal channel assignment and $L(p,1)$-labeling
A new approach on locally checkable problems
On a distance-constrained graph labeling to model cooperation
On distance labelings of amalgamations and injective labelings of general graphs
Distance two labeling on the square of a cycle
Title not available (Why is that?)
On $\lambda$-backbone coloring of cliques with tree backbones in linear time
2-distance colorings of some direct products of paths and cycles
L(2, 1)-coloring and irreducible no-hole coloring of lexicographic product of graphs
Optimal radiocoloring of trees
Title not available (Why is that?)
A new sufficient condition for a tree $T$ to have the $(2,1)$-total number $\Delta +1$
Path partition for graphs with special blocks
Nordhaus-Gaddum-type results for path covering and $L(2,1)$-labeling numbers
On the path partition number of 6‐regular graphs
On $(s,t)$-relaxed $L(2,1)$-labeling of graphs
The $S$-\textsc{labeling} problem: an algorithmic tour
Title not available (Why is that?)
On $(s,t)$-relaxed $L(1,1)$-labelling of trees
$L(2,1)$-labeling of block graphs.
Theory of computational complexity. Part 7. Transl. from the Russian
The list $L(2,1)$-labeling of planar graphs with large girth
Distance two surjective labelling of paths and interval graphs
$L(2, 1)$-labeling of the Cartesian and strong product of two directed cycles
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
Some results on distance two labelling of outerplanar graphs
$ L ( 2 , 1 )$-labeling of disk intersection graphs
Title not available (Why is that?)
Hole: An Emerging Character in the Story of Radio k-Coloring Problem
$L(3, 2, 1)$- and $L(4, 3, 2, 1)$-labeling problems on interval graphs
Gröbner bases techniques for an $S$-packing $k$-coloring of a graph
Computing L(p,1)-Labeling with Combined Parameters
Distance constrained labelings of $K_{4}$-minor free graphs
Online coloring and $L(2,1)$-labeling of unit disk intersection graphs
Parameterizing path partitions

This page was built for publication: The $L(2,1)$-Labeling Problem on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4881295)