Independence numbers of planar contact graphs
Swanepoel, K.
(2002).
Independence numbers of planar contact graphs.
Discrete and Computational Geometry,
28(4), 649-670.
https://doi.org/10.1007/s00454-002-2897-y
(2002).
Independence numbers of planar contact graphs.
Discrete and Computational Geometry,
28(4), 649-670.
https://doi.org/10.1007/s00454-002-2897-y
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 .