6533b7dbfe1ef96bd12713c7

RESEARCH PRODUCT

On Coloring Unit Disk Graphs

Gerhard WeißenfelsM. StumpfAlbert Gräf

subject

Discrete mathematicsGeneral Computer ScienceApplied MathematicsAstrophysics::Cosmology and Extragalactic AstrophysicsComplete coloring1-planar graphComputer Science ApplicationsBrooks' theoremCombinatoricsGreedy coloringIndifference graphEdge coloringChordal graphHigh Energy Physics::ExperimentGraph coloringMathematics

description

In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.

yearjournalcountryeditionlanguage
1998-03-01Algorithmica
https://doi.org/10.1007/pl00009196