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.
Radio number for trees
Fast exact algorithm for $L(2,1)$-labeling of graphs
$L(p,2,1)$-labeling of the infinite regular trees
A characterization of $\lambda _{d,1}$-minimal trees and other attainable classes
Injective coloring of planar graphs
Parameterized complexity of coloring problems: treewidth versus vertex cover
$ L ( p , q )$-labelings of subdivisions of graphs
Distance three labelings of trees
$k-L(2,1)$-labelling for planar graphs is NP-complete for $k\geq 4$
Path covering number and $L(2,1)$-labeling number of graphs
The $L(2,1)$-labeling on planar graphs
A note on the $L (2, 1)$-labelling problem of $\mathcal{G} (k, m)$
Improved upper bounds on the $L(2,1)$-labeling of the skew and converse skew product graphs
Labeling trees with a condition at distance two
The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications
$L(2,1)$-labelings on the composition of $n$ graphs
$\lambda $-backbone colorings along pairwise disjoint stars and matchings
On $L(2,1)$-labeling of generalized Petersen graphs
Graph labellings with variable weights, a survey
Labelings of Graphs with Fixed and Variable Edge-Weights
An 8-approximation algorithm for $L(2 ,1)$-labeling of unit disk graphs
Labeling bipartite permutation graphs with a condition at distance two
A note on $L (2, 1)$-labelling of trees
On $L(d,1)$-labelings of graphs
The $\Delta ^{2}$-conjecture for $L(2,1)$-labelings is true for total graphs
$L(j,k)$-labelling and maximum ordering-degrees for trees
$(2,1)$-Total number of trees with maximum degree three
An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees
Some results on the injective chromatic number of graphs
On $L(d,1)$-labeling of Cartesian product of a cycle and a path
$L(2,1)$-labeling of dually chordal graphs and strongly orderable graphs
Fast exact algorithm for $L(2,1)$-labeling of graphs
The 2-dipath chromatic number of Halin graphs
$L(2,1)$-labeling of perfect elimination bipartite graphs
Randomly colouring graphs (a combinatorial view)
The complexity of the $L(p,q)$-labeling problem for bipartite planar graphs of small degree
$L(3,2,1)$-labeling of triangular and toroidal grids
No-hole $L(2,1)$-colorings
The $L(2,1)$-labelling problem for cubic Cayley graphs on dihedral groups
On the $L(p,1)$-labelling of graphs
The $L(2,1)$-labeling on graphs and the frequency assignment problem
$L(2,1)$-labelings of Cartesian products of two cycles
Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
On $L(2,1)$-labelings of Cartesian products of paths and cycles
The game $L(d,1)$-labeling problem of graphs

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)