Labelling Graphs with a Condition at Distance 2
From MaRDI portal
Publication:4030197
DOI10.1137/0405048zbMath0767.05080MaRDI QIDQ4030197
Jerrold R. Griggs, Roger K.-C. Yeh
Publication date: 1 April 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/75e521e85a766384590b767ad9779dfc13201753
cycle; graph coloring; NP-completeness; Hamilton paths; labelling graphs; channel assignments; labelling numbers
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
On irreducible no‐hole L(2, 1)‐coloring of trees, Distance edge coloring and collision‐free communication in wireless sensor networks, On theL(2, 1)-labelling of block graphs, On Injective Colourings of Chordal Graphs, Injective coloring of planar graphs, Fixed-parameter complexity of \(\lambda\)-labelings, Labeling trees with a condition at distance two, Labeling trees with a condition at distance two, Labelling of some planar graphs with a condition at distance two, On the hole index of \(L(2,1)\)-labelings of \(r\)-regular 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, \((p,1)\)-total labelling 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, On the computational complexity of partial covers of theta graphs, A bound on the chromatic number of the square of a planar graph, The \(L(2,1)\)-labelling of trees, \(L(2,1)\)-labelings of Cartesian products of two cycles, A survey on labeling graphs with a condition at distance two, Optimal \(L(d,1)\)-labelings of certain direct products of cycles and Cartesian products of cycles, Systems of pairs of \(q\)-distant representatives, and graph colorings, Unnamed Item, On λ-coloring split, chordal bipartite and weakly chordal graphs, L(2, 1)-labellings for direct products of a triangle and a cycle, Distance three labellings for K n ×K 2, The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Δ + 2, Fast Exact Algorithm for L(2,1)-Labeling of Graphs, Channel assignment on Cayley graphs, THE GRAPH-BIN PACKING PROBLEM, Irreducibility of L(2, 1)-coloring and Inh-Colorability of Some Classes of Graphs, Radio k-Labelings for Cartesian Products of Graphs, Distance Labelling Problems for Hypercubes and Hamming Graphs – A Survey, 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, Distance Constrained Labelings of Trees, An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees, Backbone coloring for graphs with large girths, \(L(d,1)\)-labelings of the edge-path-replacement of a graph, \(L(2,1)\)-labelings on the modular product of two graphs, The \((p,q)\)-total labeling problem for trees, Exact \(\lambda\)-numbers of generalized Petersen graphs of certain higher-orders and on Möbius strips, Group path covering and \(L(j,k)\)-labelings of diameter two graphs, \(L(2,1)\)-labelling of generalized prisms, On backbone coloring of graphs, \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs, A tight upper bound on the (\(2,1\))-total labeling number of outerplanar graphs, The game \(L(d,1)\)-labeling problem of graphs, New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs, The \(\Delta ^{2}\)-conjecture for \(L(2,1)\)-labelings is true for total graphs, On critical trees labeled with a condition at distance two, \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\), Exact algorithms for \(L(2,1)\)-labeling of graphs, \(L(2,1)\)-labeling of perfect elimination bipartite graphs, Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks, On distance constrained labeling of disk graphs, Coloring the square of the Cartesian product of two cycles, On real number labelings and graph invertibility, On \(n\)-fold \(L(j,k)\)-and circular \(L(j,k)\)-labelings of graphs, List version of \(L(d,s)\)-labelings, An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees, \(L(p,q)\)-labelling of \(K_{4}\)-minor free graphs, Acyclic colorings of products of trees, The 2-dipath chromatic number of Halin graphs, \(\lambda\)-coloring matrogenic graphs, The \(L(2,1)\)-labeling on planar graphs, Mixed hypergraphs and other coloring problems, Distance-two labelings of digraphs, 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, Labelling planar graphs without 4-cycles with a condition on distance two, The \(L(2,1)\)-labeling on Cartesian sum of graphs, Distance constrained labelings of planar graphs with no short cycles, Graph labellings with variable weights, a survey, Complexity of (p,1)-total labelling, Labeling the \(r\)-path with a condition at distance two, On island sequences of labelings with a condition at distance two, Optimal radio labellings of complete \(m\)-ary trees, \(L(j,k)\)-labelling and maximum ordering-degrees for trees, (2,1)-total labelling of trees with sparse vertices of maximum degree, The \(L(h,1,1)\)-labelling problem for trees, \(L(2,1)\)-labelings on the composition of \(n\) graphs, \((2,1)\)-Total number of trees with maximum degree three, The strong chromatic index of a class of graphs, Labeling graphs with two distance constraints, The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications, Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\), A distance-labelling problem for hypercubes, On \(L(d,1)\)-labeling of Cartesian product of a cycle and a path, \(L(h,1,1)\)-labeling of outerplanar graphs, \(L(h,k)\)-labelings of Hamming graphs, A characterization of \(\lambda _{d,1}\)-minimal trees and other attainable classes, Labeling bipartite permutation graphs with a condition at distance two, Distance-two labellings of Hamming graphs, Combinatorial optimization in system configuration design, Some results on distance two labelling of outerplanar graphs, \(L(2,1)\)-labeling of strong products of cycles, On \((d,1)\)-total numbers of graphs, \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings, Distance constrained labelings of \(K_{4}\)-minor free graphs, Relating path coverings to vertex labellings with a condition at distance two, The total graph of a hypergraph, Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers, No-hole \(L(2,1)\)-colorings, Greedy \(F\)-colorings of graphs, Algorithms for graphs with small octopus, On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs, On the number of 2-packings in a connected graph, Systems of distant representatives, \(L(2,1)\)-labeling of direct product of paths and cycles, An exact algorithm for the channel assignment problem, A note on collections of graphs with non-surjective lambda labelings, Generalized list \(T\)-colorings of cycles, Theory of computational complexity. Part 7. Transl. from the Russian, On \(L(2,1)\)-labelings of Cartesian products of paths and cycles, Distance-two labelings of graphs, A channel assignment problem for optical networks modelled by Cayley graphs, Some results on the injective chromatic number of graphs, On \(L(2,1)\)-labeling of generalized Petersen graphs, Group path covering and distance two labeling of graphs, On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs, On the \(L(2,1)\)-labelings of amalgamations of graphs, Radio number for total graph of paths, New results in \(t\)-tone coloring of graphs, The \(L(2,1)\)-labelling problem for cubic Cayley graphs on dihedral groups, \(L(p,q)\)-labeling of sparse graphs, Distance two edge labelings of lattices, \((p,q)\)-total labeling of complete graphs, The \(L(2,1)\)-labeling of unigraphs, Extremal problems on consecutive \(L(2,1)\)-labelling, The minimum span of \(L(2,1)\)-labelings of certain generalized Petersen graphs, \(L(p,q)\) labeling of \(d\)-dimensional grids, \((d,1)\)-total labelling of planar graphs with large girth and high maximum degree, A linear time algorithm for \(L(2,1)\)-labeling of trees, An extremal problem on non-full colorable graphs, \(L(2, 1)\)-labelings of the edge-path-replacement of a graph, Labeling matched sums with a condition at distance two
