Premium
Extremal C 4 ‐Free/ C 5 ‐Free Planar Graphs
Author(s) -
Dowden Chris
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21991
Subject(s) - combinatorics , mathematics , planar , planar graph , discrete mathematics , graph , computer science , computer graphics (images)
We study the topic of “extremal” planar graphs, definingexP( n , H )to be the maximum number of edges possible in a planar graph on n vertices that does not contain a given graph H as a subgraph. In particular, we examine the case when H is a small cycle, obtainingexP( n , C 4 ) ≤ 15 7 ( n − 2 )for all n ≥ 4 andexP( n , C 5 ) ≤ 12 n − 33 5for all n ≥ 11 , and showing that both of these bounds are tight.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom