On the largest planar graphs with everywhere positive combinatorial curvature (extended arxiv version)

2017/08/28 by Ghidelli, Luca · 1 citation
#05B45 (Secondary) #05C10 #05C30 (Primary) #57M15 #90C05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1708.08502

Abstract

A planar PCC graph is a simple connected planar graph with everywhere positive combinatorial curvature which is not a prism or an antiprism and with all vertices of degree at least 3. We prove that every planar PCC graph has at most 208 vertices, thus answering completely a question raised by DeVos and Mohar. The proof is based on a refined discharging technique and on an accurate low-scale combinatorical description of such graphs. We also prove that all faces in a planar PCC graph have at most 41 sides, and this result is sharp as well.

Cited by

• Halin graphs with positive Lin-Lu-Yau curvature

Related

• The set of vertices with positive curvature in a planar graph with nonnegative curvature
• A curvature notion for planar graphs stable under planar duality
• On the size of planar graphs with positive Lin-Lu-Yau Ricci curvature
• The first gap for total curvatures of planar graphs with nonnegative curvature
• Total curvature of planar graphs with nonnegative combinatorial curvature