Premium
Subdivisions of K 5 in Graphs Embedded on Surfaces With Face‐Width at Least 5
Author(s) -
Krakovski Roi,
Stephens D. Christopher,
Zha Xiaoya
Publication year - 2013
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.21700
Subject(s) - subdivision , combinatorics , conjecture , mathematics , graph , face (sociological concept) , surface (topology) , discrete mathematics , geometry , geography , social science , archaeology , sociology
We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K 5 . This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K 5 . Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V (G), G contains a subdivision of K 5 whose branch vertices are v and four neighbors of v .