Independence numbers of planar contact graphs
Swanepoel, Konrad
(2002)
Independence numbers of planar contact graphs
Discrete and Computational Geometry, 28 (4).
pp. 649-670.
ISSN 0179-5376
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 .
| Item Type | Article |
|---|---|
| Departments | Mathematics |
| DOI | 10.1007/s00454-002-2897-y |
| Date Deposited | 09 Oct 2009 09:45 |
| URI | https://researchonline.lse.ac.uk/id/eprint/25408 |
Explore Further
- http://www.springer.com/math/numbers/journal/454 (Official URL)
ORCID: https://orcid.org/0000-0002-1668-887X