The $L(2,1)$-Labeling Problem on Graphs
From MaRDI portal
Publication:4881295
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
Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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) ⋮ \(L(2,1)\)-labelings of subdivisions of graphs ⋮ Improved upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs ⋮ Distance two labelling and direct products of graphs ⋮ On characterizing radio \(k\)-coloring problem by path covering problem ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ \(L(2,1)\)-labeling of interval graphs ⋮ Labelling planar graphs without 4-cycles with a condition on distance two ⋮ On a distance-constrained graph labeling to model cooperation ⋮ A note on \(L (2, 1)\)-labelling of trees ⋮ \(L(2,1)\)-labeling of Kneser graphs and coloring squares of Kneser graphs ⋮ A lower bound technique for radio \(k\)-coloring ⋮ The \(L(2,1)\)-labeling on Cartesian sum of graphs ⋮ \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s ⋮ Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks ⋮ Nordhaus-Gaddum-type results for path covering and \(L(2,1)\)-labeling numbers ⋮ New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ On the number of 2-packings in a connected graph ⋮ Distance constrained labelings of planar graphs with no short cycles ⋮ Graph labellings with variable weights, a survey ⋮ Complexity of (p,1)-total labelling ⋮ Optimal radio labellings of complete \(m\)-ary trees ⋮ \(L(j,k)\)-labelling and maximum ordering-degrees for trees ⋮ 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 ⋮ The \(\Delta ^{2}\)-conjecture for \(L(2,1)\)-labelings is true for total graphs ⋮ On distance constrained labeling of disk graphs ⋮ (2,1)-total labelling of trees with sparse vertices of maximum degree ⋮ The \(L(h,1,1)\)-labelling problem for trees ⋮ On critical trees labeled with a condition at distance two ⋮ \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs ⋮ On \(n\)-fold \(L(j,k)\)-and circular \(L(j,k)\)-labelings of graphs ⋮ \(L(2,1)\)-labelings on the composition of \(n\) graphs ⋮ The \(L(2,1)\)-labeling of unigraphs ⋮ Theory of computational complexity. Part 7. Transl. from the Russian ⋮ \((2,1)\)-Total number of trees with maximum degree three ⋮ A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\) ⋮ Frequency assignment problem in networks with limited spectrum ⋮ Labeling graphs with two distance constraints ⋮ The list \(L(2,1)\)-labeling of planar graphs with large girth ⋮ 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 ⋮ Distance two surjective labelling of paths and interval graphs ⋮ Linear and cyclic distance-three labellings of trees ⋮ On \(\text{Ł}(\wp, \wp - 1, \dots, 1)\) labelings of circulant 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 ⋮ Partial and perfect path covers of cographs ⋮ On \(L(2,1)\)-labelings of Cartesian products of paths and cycles ⋮ Some results on distance two labelling of outerplanar graphs ⋮ A note on the \(L (2, 1)\)-labelling problem of \(\mathcal{G} (k, m)\) ⋮ \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings ⋮ Distance constrained labelings of \(K_{4}\)-minor free graphs ⋮ Optimal frequency assignment and planar list \(L(2, 1)\)-labeling ⋮ Distance-two labelings of graphs ⋮ Equitable colorings of bounded treewidth graphs ⋮ List version of \(L(d,s)\)-labelings ⋮ 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 ⋮ 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
This page was built for publication: The $L(2,1)$-Labeling Problem on Graphs
