Penny graph

Every vertex in a penny graph has at most six neighboring vertices; here the number six is the kissing number for circles in the plane. However, the pennies on the boundary of the convex hull have fewer neighbors. Counting more precisely this reduction in neighbors for boundary pennies leads to a precise bound on the number of edges in any penny graph: a penny graph with n vertices has at most

$${\displaystyle \left\lfloor 3n-{\sqrt {12n-3}}\right\rfloor }$$

edges. Some penny graphs, formed by arranging the pennies in a triangular grid, have exactly this number of edges.[7][8][9]

By arranging the pennies in a square grid, or in the form of certain squaregraphs, one can form triangle-free penny graphs whose number of edges is at least

$${\displaystyle \left\lfloor 2n-2{\sqrt {n}}\right\rfloor ,}$$

and in any triangle-free penny graph the number of edges is at most[10]

$${\displaystyle 2n-1.65{\sqrt {n}}.}$$

Swanepoel conjectured that the ${\displaystyle \left\lfloor 2n-2{\sqrt {n}}\right\rfloor }$ bound is tight.[11] Proving this, or finding a better bound, remains open.

An optimal coloring of the 11-vertex penny graph shown above requires four colors

Every penny graph contains a vertex with at most three neighbors. For instance, such a vertex can be found at one of the corners of the convex hull of the circle centers. Therefore, penny graphs have degeneracy at most three. Based on this, one can prove that their graph colorings require at most four colors, much more easily than the proof of the more general four-color theorem.[12] However, despite their restricted structure, there exist penny graphs that do still require four colors.[13]

A triangle-free penny graph with the property that all the pennies on the convex hull touch at least three other pennies

Analogously, the degeneracy of every triangle-free penny graph is at most two. Every such graph contains a vertex with at most two neighbors, even though it is not always possible to find this vertex on the convex hull. Based on this, one can prove that they require at most three colors, more easily than the proof of the more general Grötzsch's theorem that triangle-free planar graphs are 3-colorable.[10]

A maximum independent set in a penny graph is a subset of the pennies, no two of which touch each other. Finding maximum independent sets is NP-hard for arbitrary graphs, and remains NP-hard on penny graphs.[2] It is an instance of the maximum disjoint set problem, in which one must find large subsets of non-overlapping regions of the plane. However, as with planar graphs more generally, Baker's technique provides a polynomial-time approximation scheme for this problem.[14]

In 1983, Paul Erdős asked for the largest number c such that every n-vertex penny graph has an independent set of at least cn vertices.[15] That is, if we place n pennies on a flat surface, there should be a subset of cn of the pennies that do not touch each other. By the four-color theorem, c ≥ 1/4, and the improved bound c ≥ 8/31 ≈ 0.258 was proven by Swanepoel.[16] In the other direction, Pach and Tóth proved that c ≤ 5/16 = 0.3125.[15] As of 2013, these remained the best bounds known for this problem.[4][17]