Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs

David Eppstein

doi:10.7155/jgaa.00463

Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs

Authors

David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00463

Keywords:

squaregraph , penny graph , triangle-free graph , unit disk contact graph , minimum-distance graph , graph degeneracy , list coloring

Abstract

We show that triangle-free penny graphs have degeneracy at most two, and that both triangle-free penny graphs and squaregraphs have at most $\min\bigl(2n-\Omega(\sqrt n),2n-D-2\bigr)$ edges, where $n$ is the number of vertices and $D$ is the diameter of the graph.

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2018-09-01

How to Cite

Eppstein, D. (2018). Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs. Journal of Graph Algorithms and Applications, 22(3), 483–499. https://doi.org/10.7155/jgaa.00463