Labelling Graphs with a Condition at Distance 2

DOI10.1137/0405048zbMATH Open0767.05080OpenAlexW2148410650MaRDI QIDQ4030197FDOQ4030197

Authors: J. Griggs, Roger K. 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

Recommendations

• \(L(2,l)\)-labellings of integer distance graphs
• scientific article; zbMATH DE number 1409224
• Distance labellings of graphs
• On \(L(d,1)\)-labelings of graphs
• On \(L(2,1)\)-labellings of distance graphs

zbMATH Keywords

graph coloringNP-completenesscycleHamilton pathslabelling graphschannel assignmentslabelling numbers

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (only showing first 100 items - show all)

• \((p,1)\)-total labelling of graphs
• Radio number for trees
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Improved bounds on the chromatic numbers of the square of Kneser graphs
• \(L(p,2,1)\)-labeling of the infinite regular trees
• A characterization of \(\lambda _{d,1}\)-minimal trees and other attainable classes
• On \((d,1)\)-total numbers of graphs
• Injective coloring of planar graphs
• Some classes of trees with maximum number of holes two
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• The \(L(2,1)\)-labeling on planar graphs
• Improved upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs
• Good edge-labelling of 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 irreducible no‐hole L(2, 1)‐coloring of trees
• Solutions of some \(L(2, 1)\)-coloring related open problems
• Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\)
• A note on \(L (2, 1)\)-labelling of trees
• The \(\Delta ^{2}\)-conjecture for \(L(2,1)\)-labelings is true for total graphs
• An \(O(n\log n)\) algorithm for finding edge span of cacti
• On \(L(k, k - 1, \ldots, 1)\) labeling of triangular lattice
• Notes on \(L(1,1)\) and \(L(2,1)\) labelings for \(n\)-cube
• Some results on the injective chromatic number of graphs
• On \(L(d,1)\)-labeling of Cartesian product of a cycle and a path
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• The 2-dipath chromatic number of Halin graphs
• On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
• Randomly colouring graphs (a combinatorial view)
• Relating path coverings to vertex labellings with a condition at distance two
• \(L(3,2,1)\)-labeling of triangular and toroidal grids
• No-hole \(L(2,1)\)-colorings
• \(L(2, 1)\)-labelings of the edge-path-replacement of a graph
• The \(L(2,1)\)-labelling problem for cubic Cayley graphs on dihedral groups
• Mixed hypergraphs and other coloring problems
• 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
• Optimal \(L(d,1)\)-labelings of certain direct products of cycles and Cartesian products of cycles
• On \(L(2,1)\)-labelings of Cartesian products of paths and cycles
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Title not available (Why is that?)
• A linear time algorithm to compute square of interval graphs and their colouring
• \((2,1)\)-total labeling of a class of subcubic graphs
• \(L(2,1)\)-labeling of direct product of paths and cycles
• A distance-labelling problem for hypercubes
• \(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
• \(L(2,1)\)-labeling of strong products of cycles
• A tight upper bound on the (\(2,1\))-total labeling number of outerplanar graphs
• A lower bound for radio \(k\)-chromatic number
• \(L(2,1)\)-labeling of interval graphs
• On some \(L(2, 1)\)-coloring parameters of certain graph classes
• Radio graceful Hamming graphs
• The strong chromatic index of a class of graphs
• An exact algorithm for the channel assignment problem
• The \(L(2,1)\)-labelling of trees
• Threshold-coloring and unit-cube contact representation of planar graphs
• Complexity of (p,1)-total labelling
• Optimal radio labellings of complete \(m\)-ary 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
• Multiple \(L(j,1)\)-labeling of the triangular lattice
• Fixed-parameter complexity of \(\lambda\)-labelings
• \(2\)-distance coloring of planar graphs with maximum degree \(5\)
• On \((s,t)\)-relaxed \(L(2,1)\)-labelings of the triangular lattice
• Optimal \(L(3, 2, 1)\)-labeling of triangular lattice
• \(L(p,q)\) labeling of \(d\)-dimensional grids
• A bound on the chromatic number of the square of a planar graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(L(2,1)\)-labeling of unigraphs
• Systems of distant representatives
• 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
• On backbone coloring of graphs
• On Injective Colourings of Chordal Graphs
• \((d,1)\)-total labelling of planar graphs with large girth and high maximum degree
• Online \(L(2,1)\)-coloring problem on paths with restricted size of memory
• \((2,1)\)-total labelling of outerplanar graphs
• On irreducible no-hole \(L(2, 1)\)-labelings of hypercubes and triangular lattices
• \(L(p,q)\)-labeling of a graph embeddable on the torus
• Locally injective \(k\)-colourings of planar graphs
• \( L ( p , q )\)-labelings of subdivisions of graphs
• New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs
• Path covering number and \(L(2,1)\)-labeling number of graphs
• On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs
• On the \(L(2, 1)\)-labelling of block graphs
• Distance three labellings for \(K _n\times K_2\)
• A note on the \(L (2, 1)\)-labelling problem of \(\mathcal{G} (k, m)\)
• On \(L(2,1)\)-labeling of generalized Petersen graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• Graph labellings with variable weights, a survey

This page was built for publication: Labelling Graphs with a Condition at Distance 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4030197)