Resource title

Independence numbers of planar contact graphs

Resource image

image for OpenScout resource :: Independence numbers of planar contact graphs

Resource description

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 .

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/25408/

Resource license