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

DOI10.1007/978-3-319-73915-1_39MaRDI QIDQ4625139zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.05152

zbMATH Keywords

diameterlist coloring number

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: We show that triangle-free penny graphs have degeneracy at most two, list coloring number (choosability) at most three, diameter $D=Omega(sqrtn)$, and at most $$ edges.

Cites work

• 3-choosability of triangle-free planar graphs with constraints on 4-cycles
• A not 3-choosable planar graph without 3-cycles
• A short list color proof of Grötzsch's theorem
• Colorings and orientations of graphs
• Combinatorial properties of triangle-free rectangle arrangements and the squarability problem
• Combinatorics and geometry of finite and infinite squaregraphs
• Contact Graphs of Circular Arcs
• Contact graphs of line segments are NP-complete
• Densities of minor-closed graph families
• Graphs drawn with few crossings per edge
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• scientific article; zbMATH DE number 739029 (Why is no real title available?)
• scientific article; zbMATH DE number 2107985 (Why is no real title available?)
• scientific article; zbMATH DE number 7662675 (Why is no real title available?)
• On the density of maximal 1-planar graphs
• On the independence number of minimum distance graphs
• On the maximum number of edges in quasi-planar graphs
• On Triangle Contact Graphs
• Quasi-planar graphs have a linear number of edges
• Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
• Rectangular layouts and contact graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Three-coloring triangle-free planar graphs in linear time
• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count

Cited in

(5)

• Discrete harmonic functions on infinite penny graphs
• On arrangements of orthogonal circles
• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count
• Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
• Harmonic functions of polynomial growth on infinite penny graphs

This page was built for publication: Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625139)