Approximations for -Colorings of Graphs

DOI10.1093/comjnl/47.2.193zbMath1039.68090OpenAlexW2025000920MaRDI QIDQ4470433

Ton Kloks, Jan van Leeuwen, Richard B. Tan, Hans L. Bodlaender

Publication date: 1 July 2004

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/47.2.193

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (52)

An O$(n^{1.75})$ algorithm for $L(2,1)$-labeling of trees ⋮ $L(2, 1)$-labeling of circulant graphs ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ $L(3,2,1)$-labeling of triangular and toroidal grids ⋮ A linear time algorithm for $L(2,1)$-labeling of trees ⋮ L(3,1)-labeling of circulant graphs ⋮ Computational complexity of distance edge labeling ⋮ Unnamed Item ⋮ Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs ⋮ Exact square coloring of subcubic planar graphs ⋮ Facial $L(2, 1)$-edge-labelings of trees ⋮ $k-L(2,1)$-labelling for planar graphs is NP-complete for $k\geq 4$ ⋮ $L(2, 1)$-labeling of the Cartesian and strong product of two directed cycles ⋮ $L(3, 2, 1)$- and $L(4, 3, 2, 1)$-labeling problems on interval graphs ⋮ Fast exact algorithm for $L(2,1)$-labeling of graphs ⋮ Online $L(2,1)$-coloring problem on paths with restricted size of memory ⋮ Locally injective $k$-colourings of planar graphs ⋮ An 8-approximation algorithm for $L(2 ,1)$-labeling of unit disk graphs ⋮ $L(0,1)$-labelling of permutation graphs ⋮ L(2,1,1)-labeling of interval graphs ⋮ Exact algorithms for $L(2,1)$-labeling of graphs ⋮ Unnamed Item ⋮ An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees ⋮ Group path covering and distance two labeling of graphs ⋮ $L(2,1)$-labeling of dually chordal graphs and strongly orderable graphs ⋮ The $L(2,1)$-labelling problem for cubic Cayley graphs on dihedral groups ⋮ Determining the $L(2,1)$-span in polynomial space ⋮ Computing $L(p, 1)$-labeling with combined parameters ⋮ $L(1,1)$-labelling of the direct product of a complete graph and a cycle ⋮ $L(2,1)$-labeling of interval graphs ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ On a distance-constrained graph labeling to model cooperation ⋮ Improved self-stabilizing algorithms for $L(2, 1)$-labeling tree networks ⋮ On $L(2,1)$-coloring split, chordal bipartite, and weakly chordal graphs ⋮ Graph labellings with variable weights, a survey ⋮ $L(2, 1)$-labeling of permutation and bipartite permutation graphs ⋮ On $n$-fold $L(j,k)$-and circular $L(j,k)$-labelings of graphs ⋮ On $(s,t)$-relaxed $L(2,1)$-labeling of graphs ⋮ $L(2,1)$-labeling for brick product graphs ⋮ $L(1, 2)$-edge-labelings for lattices ⋮ On Injective Colourings of Chordal Graphs ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Distance two surjective labelling of paths and interval graphs ⋮ On the advice complexity of the online $L(2,1)$-coloring problem on paths and cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ $L(h,1,1)$-labeling of outerplanar graphs ⋮ 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 ⋮ Combinatorial optimization in system configuration design ⋮ On λ-coloring split, chordal bipartite and weakly chordal graphs ⋮ Injective colouring for H-free graphs ⋮ List version of $L(d,s)$-labelings

This page was built for publication: Approximations for -Colorings of Graphs