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

David Eppstein

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\bigl(2n-\Omega(\sqrt n),2n-D-2\bigr)$ edges.

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment