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)

Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
$L(2,1)$-labelings of Cartesian products of two cycles
Labelled (Hyper)Graphs, Negotiations and the Naming Problem
On L(2,1)-labelings of Cartesian products of paths and cycles
scientific article; zbMATH DE number 5237265 (Why is no real title available?)
The game $L(d,1)$-labeling problem of graphs
Algorithms for graphs with small octopus
Linear and cyclic distance-three labellings of trees
Group path covering and distance two labeling of graphs
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
$L(2,1)$-labeling of direct product of paths and cycles
An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
The (p,q)-total labeling problem for trees
The list $L(2,1)$-labeling of planar graphs with large girth
Distance two surjective labelling of paths and interval graphs
L(h,1,1)-labeling of outerplanar graphs
The $L(h,1,1)$-labelling problem for trees
Labelling planar graphs without 4-cycles with a condition on distance two
$L(2, 1)$-labeling of the Cartesian and strong product of two directed cycles
$L(3,1)$-labeling of circulant graphs
Distance constrained labelings of planar graphs with no short cycles
$L(2,1)$-labelings of subdivisions of graphs
L(2,1)-labeling of interval graphs
Distance-two labellings of Hamming graphs
$(2,1)$-total labeling of trees with large maximum degree
Characterization results for the $L(2, 1, 1)$-labeling problem on trees
A complete $L (2, 1)$ span characterization for small trees
Injective colorings with arithmetic constraints
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
Some results on distance two labelling of outerplanar graphs
Frequency assignment problem in networks with limited spectrum
$ L ( 2 , 1 )$-labeling of disk intersection graphs
Distance-two labelings of graphs
The L(2,1)-labelling of trees
$L (j, k)$- and circular $L(j, k)$-labellings for the products of complete graphs
scientific article; zbMATH DE number 7318748 (Why is no real title available?)
Complexity of (p,1)-total labelling
Optimal radio labellings of complete m-ary trees
On distance constrained labeling of disk graphs
scientific article; zbMATH DE number 7478538 (Why is no real title available?)
Recent progress in mathematics and engineering on optimal graph labellings with distance conditions
On characterizing radio $k$-coloring problem by path covering problem
Systems of pairs of $q$-distant representatives, and graph colorings
A note on the chromatic number of the square of Kneser graph $K(2 k + 1, k)$
$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
Hole: An Emerging Character in the Story of Radio k-Coloring Problem
Gröbner bases techniques for an $S$-packing $k$-coloring of a graph
Exact algorithms for $L(2,1)$-labeling of graphs
A Linear Time Algorithm for L(2,1)-Labeling of Trees
Distance constrained labelings of $K_{4}$-minor free graphs
A survey on labeling graphs with a condition at distance two
A new approach to the chromatic number of the square of Kneser graph $K(2k+1,k)$
$L(p,q)$-labeling of sparse graphs
Computing L(p,1)-Labeling with Combined Parameters
Online coloring and $L(2,1)$-labeling of unit disk intersection graphs
$L(3,2,1)$-labeling for cylindrical grid: the Cartesian product of a path and a cycle
Parameterizing path partitions
Radio number for total graph of paths
On the $k$-path cover problem for cacti
n-fold L(2, 1)-labelings of Cartesian product of paths and cycles
Fixed-parameter complexity of $\lambda$-labelings
A New Point of NP-Hardness for 2-to-1 Label Cover
$L(2,1)$-labeling for subdivisions of cycle dominated graphs
The L(2,1)-labeling and operations of graphs
Distance Constrained Labelings of Trees
$L(p,q)$ labeling of $d$-dimensional grids
L(2,1)-labeling of Kneser graphs and coloring squares of Kneser graphs
A lower bound technique for radio k-coloring
A bound on the chromatic number of the square of a planar graph
Distance two labelling and direct products of graphs
Optimal frequency assignment and planar list $L(2, 1)$-labeling
Algorithms for solving problems on graphs of bounded pathwidth
List version of L(d,s)-labelings
Backbone coloring for graphs with large girths
L(2,1)-labelings on the modular product of two graphs
The path-partition problem in block graphs
Labeling planar graphs with a condition at distance two
Parameterized complexity of distance labeling and uniform channel assignment problems
The $L(2,1)$-labeling of unigraphs
Systems of distant representatives
On backbone coloring of graphs
On the $k$-path partition of graphs.
Radio $k$-labeling of paths
scientific article; zbMATH DE number 5583498 (Why is no real title available?)
On the L(h,k)-Labeling of Co-comparability Graphs
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$

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)