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

DOI10.1137/S0895480193245339zbMath0860.05064OpenAlexW2085421834MaRDI QIDQ4881295

No author found.

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

zbMATH Keywords

labeling polynomial time algorithm trees chordal graphs cographs

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

A new sufficient condition for a tree $T$ to have the $(2,1)$-total number $\Delta +1$ ⋮ OPTIMAL RADIOCOLORING OF TREES ⋮ 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 ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ A linear time algorithm for $L(2,1)$-labeling of trees ⋮ L(3,1)-labeling of circulant graphs ⋮ An extremal problem on non-full colorable graphs ⋮ Hole: An Emerging Character in the Story of Radio k-Coloring Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs ⋮ Gröbner bases techniques for an $S$-packing $k$-coloring of a graph ⋮ $ L ( p , q )$-labelings of subdivisions of graphs ⋮ $L(2, 1)$-labeling of the Cartesian and strong product of two directed cycles ⋮ 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 ⋮ L(2, 1)-coloring and irreducible no-hole coloring of lexicographic product of graphs ⋮ On the path partition number of 6‐regular graphs ⋮ An 8-approximation algorithm for $L(2 ,1)$-labeling of unit disk graphs ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ Distance Constrained Labelings of Trees ⋮ An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees ⋮ Unnamed Item ⋮ List backbone colouring of graphs ⋮ Path covering number and $L(2,1)$-labeling number of graphs ⋮ On theL(2, 1)-labelling of block 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 ⋮ Fast Exact Algorithm for L(2,1)-Labeling 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 ⋮ Radio $k$-labeling of paths ⋮ Injective coloring of planar 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 ⋮ Fixed-parameter complexity of $\lambda$-labelings ⋮ n-fold L(2, 1)-labelings of Cartesian product of paths and cycles ⋮ L(1,1)-Labeling of direct product of cycles ⋮ $L(p,q)$-labeling and integer tension of a graph embedded on torus ⋮ On $(s,t)$-relaxed $L(2,1)$-labeling of graphs ⋮ A sufficient condition for a tree to be $(\Delta+1)$-$(2,1)$-totally labelable ⋮ Labeling trees with a condition at distance two ⋮ DISTANCE TWO LABELING ON THE SQUARE OF A CYCLE ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ On (s,t)-relaxed L(1,1)-labelling of trees ⋮ Labeling trees with a condition at distance two ⋮ Systems of pairs of $q$-distant representatives, and graph colorings ⋮ 2-distance colorings of some direct products of paths and cycles ⋮ 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 ⋮ $(2,1)$-total labeling of trees with large maximum degree ⋮ $L(3,2,1)$-labeling for Cylindrical grid: the cartesian product of a path and a cycle ⋮ A new approach on locally checkable problems ⋮ Optimal channel assignment and $L(p,1)$-labeling ⋮ An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees ⋮ $L(2, 1)$-labeling of circulant graphs ⋮ The path-partition problem in block graphs ⋮ $L(3,2,1)$-labeling of triangular and toroidal grids ⋮ $L(p,q)$-labelling of $K_{4}$-minor free graphs ⋮ The 2-dipath chromatic number of Halin graphs ⋮ $L(2,1)$-labeling for subdivisions of cycle dominated graphs ⋮ $\lambda$-coloring matrogenic graphs ⋮ The $L(2,1)$-labeling on planar graphs ⋮ $k$-path partitions in trees ⋮ $k-L(2,1)$-labelling for planar graphs is NP-complete for $k\geq 4$ ⋮ Distance-two labelings of digraphs ⋮ Backbone coloring for graphs with large girths ⋮ $L(2,1)$-labelings on the modular product of two graphs ⋮ Some results on the injective chromatic number of graphs ⋮ On $L(2,1)$-labeling of generalized Petersen graphs ⋮ Fast exact algorithm for $L(2,1)$-labeling of graphs ⋮ $L(p,2,1)$-labeling of the infinite regular trees ⋮ The $(p,q)$-total labeling problem for trees ⋮ A complete $L (2, 1)$ span characterization for small trees ⋮ Injective colorings with arithmetic constraints ⋮ On the $k$-path partition of graphs. ⋮ Distance three labelings of trees ⋮ Exact algorithms for $L(2,1)$-labeling of graphs ⋮ Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers ⋮ Group path covering and distance two labeling of graphs ⋮ No-hole $L(2,1)$-colorings ⋮ On backbone coloring of graphs ⋮ $L(2,1)$-labeling of dually chordal graphs and strongly orderable graphs ⋮ Radio number for total graph of paths ⋮ $L(2,1)$-labeling of perfect elimination bipartite graphs ⋮ The $L(2,1)$-labelling problem for cubic Cayley graphs on dihedral groups ⋮ $L(p,q)$-labeling of sparse graphs ⋮ Algorithms for graphs with small octopus ⋮ The game $L(d,1)$-labeling problem of graphs ⋮ Randomly colouring graphs (a combinatorial view)

This page was built for publication: The $L(2,1)$-Labeling Problem on Graphs