Subdivisions ofK5in Graphs Embedded on Surfaces With Face-Width at Least 5

Autor:	Roi Krakovski, D. Christopher Stephens, Xiaoya Zha
Rok vydání:	2012
Předmět:	Discrete mathematics Combinatorics Conjecture business.industry Discrete Mathematics and Combinatorics Geometry and Topology Special case business Graph Mathematics Subdivision
Zdroj:	Journal of Graph Theory. 74:182-197
ISSN:	0364-9024
Popis:	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 K5. This is a special case of a conjecture of P. Seymour, that every 5-connected nonplanar graph contains a subdivision of K5. 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 K5 whose branch vertices are v and four neighbors of v.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c3bdb28e6eaed3187e9a727e177aa663 https://doi.org/10.1002/jgt.21700 Zobrazit plný text záznamu Plný text