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)

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
Group path covering and distance two labeling of graphs
$L(2,1)$-labeling of direct product of paths and cycles
$L(h,1,1)$-labeling of outerplanar graphs
The $(p,q)$-total labeling problem for trees
The $L(h,1,1)$-labelling problem for trees
$(2,1)$-total labeling of trees with large maximum degree
$L(2,1)$-labelings of subdivisions of graphs
$L(2,1)$-labeling of interval graphs
Characterization results for the $L(2, 1, 1)$-labeling problem on trees
The $L(2,1)$-labelling of trees
$L (j, k)$- and circular $L(j, k)$-labellings for the products of complete graphs
Complexity of (p,1)-total labelling
Optimal radio labellings of complete $m$-ary trees
On distance constrained labeling of disk graphs
Systems of pairs of $q$-distant representatives, and graph colorings
On characterizing radio $k$-coloring problem by path covering problem
A Linear Time Algorithm for L(2,1)-Labeling of Trees
A survey on labeling graphs with a condition at distance two
Exact algorithms for $L(2,1)$-labeling of graphs
$L(3,2,1)$-labeling for cylindrical grid: the Cartesian product of a path and a cycle
$L(p,q)$-labeling of sparse graphs
Fixed-parameter complexity of $\lambda$-labelings
$L(2,1)$-labeling for subdivisions of cycle dominated graphs
The L(2,1)-labeling and operations of graphs
$L(p,q)$ labeling of $d$-dimensional grids
A bound on the chromatic number of the square of a planar graph
Algorithms for solving problems on graphs of bounded pathwidth
Labeling planar graphs with a condition at distance two
The $L(2,1)$-labeling of unigraphs
Systems of distant representatives
Backbone coloring for graphs with large girths
$L(2,1)$-labelings on the modular product of two graphs
On backbone coloring of graphs
On the L(h,k)-Labeling of Co-comparability Graphs
$(2,1)$-total labelling of outerplanar graphs
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

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)