Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count

Abstract

We show that triangle-free penny graphs have degeneracy at most two, list coloring number (choosability) at most three, diameter $D=\Omega (\sqrt{n})$, and at most $\min (2n-\Omega (\sqrt{n}),2n-D-2)$ edges.

10 pages, 2 figures. To appear at the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Cited by in corpus (2)

• General penny graphs are at most 43/18-dense
• On the Colin de Verdiere graph number and penny graphs