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

DOI10.1137/S0895480193245339MaRDI QIDQ4881295zbMATH OpenOpenAlexFDO

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

chordal graphs cographs labeling polynomial time algorithm trees

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

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

Cited in

(only showing first 100 items - show all)

The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications
On $L(d,1)$-labeling of Cartesian product of a cycle and a path
L(h,1,1)-labeling of outerplanar graphs
L(h,k)-labelings of Hamming graphs
A characterization of $\lambda _{d,1}$-minimal trees and other attainable classes
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
Labeling bipartite permutation graphs with a condition at distance two
Distance-two labellings of Hamming graphs
Some results on distance two labelling of outerplanar graphs
-backbone colorings along pairwise disjoint stars and matchings
Distance constrained labelings of $K_{4}$-minor free graphs
Partial and perfect path covers of cographs
The path-partition problem in block graphs
$k$-path partitions in trees
On the $k$-path partition of graphs.
Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
No-hole $L(2,1)$-colorings
Algorithms for graphs with small octopus
On $L(d,1)$-labelings of graphs
Optimal channel assignment and $L(p,1)$-labeling
$L(2, 1)$-labeling of circulant graphs
The $S$-\textsc{labeling} problem: an algorithmic tour
$L(2,1)$-labeling for subdivisions of cycle dominated graphs
$L(3, 2, 1)$- and $L(4, 3, 2, 1)$-labeling problems on interval graphs
$L(2, 1)$-labelling of graphs with few $P_4$'s
On the number of 2-packings in a connected graph
Systems of distant representatives
$L(2,1)$-labeling of direct product of paths and cycles
A note on collections of graphs with non-surjective lambda labelings
Path partition for graphs with special blocks
Theory of computational complexity. Part 7. Transl. from the Russian
Frequency assignment problem in networks with limited spectrum
On L(2,1)-labelings of Cartesian products of paths and cycles
Distance-two labelings of graphs
Some results on the injective chromatic number of graphs
On $L(2,1)$-labeling of generalized Petersen graphs
Group path covering and distance two labeling of graphs
Radio number for total graph of paths
The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups
L(p,q)-labeling of sparse graphs
$L(2, 1)$-labeling of permutation and bipartite permutation graphs
The list $L(2,1)$-labeling of planar graphs with large girth
Distance two surjective labelling of paths and interval graphs
On $\text{Ł}(\wp, \wp - 1, \dots, 1)$ labelings of circulant graphs
A note on the $L (2, 1)$-labelling problem of $\mathcal{G} (k, m)$
Optimal frequency assignment and planar list L(2, 1)-labeling
A new approach on locally checkable problems
Computing $L(p, 1)$-labeling with combined parameters
On a distance-constrained graph labeling to model cooperation
Nordhaus-Gaddum-type results for path covering and $L(2,1)$-labeling numbers
The $L(2,1)$-labeling of unigraphs
A note on the chromatic number of the square of Kneser graph $K(2 k + 1, k)$
$ L ( 2 , 1 )$-labeling of disk intersection graphs
2-distance colorings of some direct products of paths and cycles
$(2,1)$-total labeling of trees with large maximum degree
On distance labelings of amalgamations and injective labelings of general graphs
A new sufficient condition for a tree $T$ to have the $(2,1)$-total number $\Delta +1$
Characterization results for the $L(2, 1, 1)$-labeling problem on trees
On the $k$-path cover problem for cacti
Extremal problems on consecutive $L(2,1)$-labelling
L(p,q) labeling of d-dimensional grids
A linear time algorithm for L(2,1)-labeling of trees
An extremal problem on non-full colorable graphs
Gröbner bases techniques for an $S$-packing $k$-coloring of a graph
A new approach to the chromatic number of the square of Kneser graph $K(2k+1,k)$
Parameterized complexity of distance labeling and uniform channel assignment problems
List backbone colouring of graphs
Path covering number and $L(2,1)$-labeling number of graphs
Labeling planar graphs with a condition at distance two
$(2,1)$-total labelling of outerplanar graphs
The $L(2,1)$-labeling on the skew and converse skew products of graphs
Radio number for trees
Recent progress in mathematics and engineering on optimal graph labellings with distance conditions
$L (j, k)$- and circular $L(j, k)$-labellings for the products of complete graphs
The $L(2,1)$-labeling on graphs and the frequency assignment problem
On the $L(p,1)$-labelling of graphs
A bound on the chromatic number of the square of a planar graph
The L(2,1)-labelling of trees
Hamiltonian path saturated graphs with small size
$L(2,1)$-labelings of Cartesian products of two cycles
A survey on labeling graphs with a condition at distance two
Systems of pairs of $q$-distant representatives, and graph colorings
$ L ( p , q )$-labelings of subdivisions of graphs
$L(2, 1)$-labeling of the Cartesian and strong product of two directed cycles
L(2,1)-labeling of block graphs.
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
Fast exact algorithm for $L(2,1)$-labeling of graphs
L(3,2,1)-labeling of triangular and toroidal grids
A New Point of NP-Hardness for 2-to-1 Label Cover
scientific article; zbMATH DE number 7404291 (Why is no real title available?)
Irreducibility of L(2, 1)-coloring and Inh-Colorability of Some Classes of Graphs
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
The L(d₁,d₂)-labeling problem on graphs
Distance Constrained Labelings of Trees
An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
Labelings of Graphs with Fixed and Variable Edge-Weights
Labelled (Hyper)Graphs, Negotiations and the Naming Problem
α2-labeling of graphs
On the L(h,k)-Labeling of Co-comparability Graphs
A Linear Time Algorithm for L(2,1)-Labeling of Trees

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)