TY - JOUR

T1 - On the number of vertices of positively curved planar graphs

AU - Oh, Byung Geun

PY - 2017/6/1

Y1 - 2017/6/1

N2 - For a connected simple graph embedded into a 2-sphere, we show that the number of vertices of the graph is less than or equal to 380 if the degree of each vertex is at least three, the combinatorial vertex curvature is positive everywhere, and the graph is different from prisms and antiprisms. This gives a new upper bound for the constant brought up by DeVos and Mohar in their paper from 2007. We also show that if a graph is embedded into a projective plane instead of a 2-sphere but satisfies the other properties listed above, then the number of vertices is at most 190.

AB - For a connected simple graph embedded into a 2-sphere, we show that the number of vertices of the graph is less than or equal to 380 if the degree of each vertex is at least three, the combinatorial vertex curvature is positive everywhere, and the graph is different from prisms and antiprisms. This gives a new upper bound for the constant brought up by DeVos and Mohar in their paper from 2007. We also show that if a graph is embedded into a projective plane instead of a 2-sphere but satisfies the other properties listed above, then the number of vertices is at most 190.

KW - Combinatorial curvature

KW - Discharging method

KW - Planar graph

UR - http://www.scopus.com/inward/record.url?scp=85013890725&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2017.01.025

DO - 10.1016/j.disc.2017.01.025

M3 - Article

AN - SCOPUS:85013890725

VL - 340

SP - 1300

EP - 1310

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 6

ER -