On coloring unit disk graphs

DOI10.1007/PL00009196MaRDI QIDQ1386337zbMATH OpenFDO

Authors D. Massart

Publication date 24 May 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009196

zbMATH Keywords

coloring problemUD graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1769307
• scientific article; zbMATH DE number 1507300
• Simple heuristics for unit disk graphs
• Improper coloring of unit disk graphs
• Distributed coloring and the local structure of unit-disk graphs

Cited in

(42)

• Maximum scan statistics and channel assignment problems in homogeneous wireless networks
• Conflict-free coloring of unit disks
• Perfectness and imperfectness of unit disk graphs on triangular lattice points
• Unit disk graphs
• 3-coloring arrangements of line segments with 4 slopes is hard
• Graph imperfection. I
• The on-line first-fit algorithm for radio frequency assignment problems.
• Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
• Approximate strong edge-colouring of unit disk graphs
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A tight bound for online colouring of disk graphs
• Local 7-coloring for planar subgraphs of unit disk graphs
• The number of disk graphs
• On some applications of the selective graph coloring problem
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• On the minimum and maximum selective graph coloring problems in some graph classes
• Clique number and ball containment number of unit ball graphs
• Multicoloring unit disk graphs on triangular lattice points
• Improper coloring of unit disk graphs
• Inverse chromatic number problems in interval and permutation graphs
• Improper Colourings of Unit Disk Graphs
• A lower bound on the area of a 3-coloured disk packing
• Bisectored unit disk graphs
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• scientific article; zbMATH DE number 1769307 (Why is no real title available?)
• Online coloring and L(2,1)-labeling of unit disk intersection graphs
• Fine-grained complexity of coloring unit disks and balls
• Fine-grained complexity of coloring unit disks and balls
• Note on coloring of double disk graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Local construction and coloring of spanners of location aware unit disk graphs
• On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
• Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
• Location-oblivious distributed unit disk graph coloring
• Distributed coloring and the local structure of unit-disk graphs
• Distributed coloring and the local structure of unit-disk graphs
• On embeddability of unit disk graphs onto straight lines
• Online dominating set and coloring
• On the chromatic number of random geometric graphs
• Classifying convex bodies by their contact and intersection graphs
• Minimum ply covering of points with disks and squares
• Coloring the complements of intersection graphs of geometric figures

This page was built for publication: On coloring unit disk graphs

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