\(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)

DOI10.1016/j.dam.2010.06.016zbMath1209.05211arXiv0909.2613MaRDI QIDQ602756

Steven D. Noble, Nicole Eggemann, Frédéric Havet

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0909.2613

zbMATH Keywords

NP-complete; planar graph; frequency assignment problem; \(L(2, 1)\)-labelling

Mathematics Subject Classification ID

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Computing L(p,1)-Labeling with Combined Parameters, On \((s,t)\)-relaxed \(L(2,1)\)-labeling of graphs, Fast exact algorithm for \(L(2,1)\)-labeling of graphs, On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs, Computing \(L(p, 1)\)-labeling with combined parameters, Subexponential algorithms for variants of the homomorphism problem in string graphs, \( L ( 2 , 1 )\)-labeling of disk intersection graphs, Determining the \(L(2,1)\)-span in polynomial space

Cites Work

• Unnamed Item
• Unnamed Item
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• Complexity of (p,1)-total labelling
• \(L(h,1)\)-labeling subclasses of planar graphs
• Labeling planar graphs with a condition at distance two
• A survey on labeling graphs with a condition at distance two
• Radiocoloring in planar graphs: Complexity and approximations
• List Colouring Squares of Planar Graphs
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• Labelling Graphs with a Condition at Distance 2
• Approximations for  -Colorings of Graphs
• Coloring the square of a planar graph
• The $L(2,1)$-Labeling Problem on Graphs
• The complexity of satisfiability problems
• Automata, Languages and Programming
• Fixed-parameter complexity of \(\lambda\)-labelings