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

labeling trees chordal graphs cographs polynomial time algorithm

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

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)

L(p,2,1)-labeling of the infinite regular trees
The $L(2,1)$-labeling on Cartesian sum of graphs
$(2,1)$-total labelling of outerplanar graphs
Radio number for trees
Fast exact algorithm for $L(2,1)$-labeling of graphs
scientific article; zbMATH DE number 7404291 (Why is no real title available?)
The weak $(2, 2)$-labelling problem for graphs with forbidden induced structures
A characterization of $\lambda _{d,1}$-minimal trees and other attainable classes
Parameterized complexity of coloring problems: treewidth versus vertex cover
Irreducibility of L(2, 1)-coloring and Inh-Colorability of Some Classes of Graphs
Distance three labelings of trees
$k-L(2,1)$-labelling for planar graphs is NP-complete for $k\geq 4$
New upper bounds on the $L(2,1)$-labeling of the skew and converse skew product graphs
On a labeling problem in graphs
$ L ( p , q )$-labelings of subdivisions of graphs
The $L(2,1)$-labeling on planar graphs
Injective coloring of planar graphs
Path covering number and $L(2,1)$-labeling number of graphs
Improved upper bounds on the $L(2,1)$-labeling of the skew and converse skew product graphs
A note on the $L (2, 1)$-labelling problem of $\mathcal{G} (k, m)$
$L(p,q)$-labeling and integer tension of a graph embedded on torus
The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications
$L(2,1)$-labelings on the composition of $n$ graphs
On the $L(2, 1)$-labelling of block graphs
$\lambda $-backbone colorings along pairwise disjoint stars and matchings
List backbone colouring of graphs
Improved self-stabilizing algorithms for $L(2, 1)$-labeling tree networks
On $L(2,1)$-labeling of generalized Petersen graphs
Labeling trees with a condition at distance two
Equitable colorings of bounded treewidth graphs
$L(2, 1)$-labeling of permutation and bipartite permutation graphs
Graph labellings with variable weights, a survey
Some open problems on graph labelings
Graph covers: where topology meets computer science, and simple means difficult
Labelings of Graphs with Fixed and Variable Edge-Weights
scientific article; zbMATH DE number 7081025 (Why is no real title available?)
The $L(2,1)$-labeling on the skew and converse skew products of graphs
α2-labeling of graphs
(2,1)-total labelling of trees with sparse vertices of maximum degree
Labeling bipartite permutation graphs with a condition at distance two
$L(p,q)$-labelling of $K_{4}$-minor free graphs
An 8-approximation algorithm for $L(2 ,1)$-labeling of unit disk graphs
A note on $L (2, 1)$-labelling of trees
The $\Delta ^{2}$-conjecture for $L(2,1)$-labelings is true for total graphs
On critical trees labeled with a condition at distance two
On $L(d,1)$-labelings of graphs
Computing $L(p, 1)$-labeling with combined parameters
$L(j,k)$-labelling and maximum ordering-degrees for trees
scientific article; zbMATH DE number 2016729 (Why is no real title available?)
$(2,1)$-Total number of trees with maximum degree three
On $n$-fold $L(j,k)$-and circular $L(j,k)$-labelings 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
On the number of 2-packings in a connected graph
Partial and perfect path covers of cographs
An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees
Optimal channel assignment and $L(p,1)$-labeling
Labeling trees with a condition at distance two
$\lambda$-coloring matrogenic graphs
A note on collections of graphs with non-surjective lambda labelings
A sufficient condition for a tree to be $(\Delta+1)$-$(2,1)$-totally labelable
A new approach on locally checkable problems
On a distance-constrained graph labeling to model cooperation
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
A linear time algorithm for L(2,1)-labeling of trees
Extremal problems on consecutive $L(2,1)$-labelling
On distance labelings of amalgamations and injective labelings of general graphs
An extremal problem on non-full colorable graphs
Fast exact algorithm for L(2,1)-labeling of graphs
$L(h,k)$-labelings of Hamming graphs
Distance two labeling on the square of a cycle
The $L(d_1,d_2)$-labeling problem on graphs
2-distance colorings of some direct products of paths and cycles
Labeling graphs with two distance constraints
scientific article; zbMATH DE number 7688018 (Why is no real title available?)
The 2-dipath chromatic number of Halin graphs
L(2,1)-labeling of perfect elimination bipartite graphs
On $\lambda$-backbone coloring of cliques with tree backbones in linear time
Randomly colouring graphs (a combinatorial view)
L(2, 1)-coloring and irreducible no-hole coloring of lexicographic product of graphs
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
Optimal radiocoloring of trees
No-hole $L(2,1)$-colorings
A new sufficient condition for a tree $T$ to have the $(2,1)$-total number $\Delta +1$
scientific article; zbMATH DE number 5026592 (Why is no real title available?)
On $\text{Ł}(\wp, \wp - 1, \dots, 1)$ labelings of circulant graphs
Path partition for graphs with special blocks
$k$-path partitions in trees
Nordhaus-Gaddum-type results for path covering and $L(2,1)$-labeling numbers
Hamiltonian path saturated graphs with small size
Distance-two labelings of digraphs
The $L(2,1)$-labelling problem for cubic Cayley graphs on dihedral groups
On $(s,t)$-relaxed $L(2,1)$-labeling of graphs
On the path partition number of 6‐regular graphs
$L(2, 1)$-labeling of circulant graphs
The $S$-\textsc{labeling} problem: an algorithmic tour
On the $L(p,1)$-labelling of graphs
The $L(2,1)$-labeling on graphs and the frequency assignment problem

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)