Independence numbers of planar contact graphs

Swanepoel, KonradORCID logo (2002) Independence numbers of planar contact graphs Discrete and Computational Geometry, 28 (4). pp. 649-670. ISSN 0179-5376
Copy

We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n .

Full text not available from this repository.

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads