\( L ( 2 , 1 )\)-labeling of disk intersection graphs

DOI10.1016/j.dam.2019.08.020zbMath1435.05171MaRDI QIDQ2306585

Konstanty Junosza-Szaniawski, Joanna Chybowska-Sokół, Paweł Rzążewski

Publication date: 23 March 2020

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

Full work available at URL: https://doi.org/10.1016/j.dam.2019.08.020

zbMATH Keywords

\( L ( 2, 1 )\)-labeling

Mathematics Subject Classification ID

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

05C07: Vertex degrees

05C76: Graph operations (line graphs, products, etc.)

Related Items

An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs, On the universality and extremality of graphs with a distance constrained colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sphere and dot product representations of graphs
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• On distance constrained labeling of disk graphs
• The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications
• Unit disk graphs
• \(T\)-colorings of graphs: recent results and open problems
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• OVSF-CDMA code assignment in wireless ad hoc networks
• On the \(L(p,1)\)-labelling of graphs
• Griggs and Yeh's Conjecture and $L(p,1)$-labelings
• Labelling Graphs with a Condition at Distance 2
• A Theorem about the Channel Assignment Problem
• Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs
• Coloring the square of a planar graph
• Approximation and Online Algorithms
• Representing graphs by disks and balls (a survey of recognition-complexity results)