The excluded minor structure theorem with planarly embedded wall

Bojan Mohar

Abstract


A graph is “nearly embedded” in a surface if it consists of graph G0 that is embedded in the surface, together with a bounded number of vortices having no large transactions. It is shown that every large wall (or grid minor) in a nearly embedded graph, many rows of which intersect the embedded subgraph G0 of the near-embedding, contains a large subwall that is planarly embedded within G0. This result provides some hidden details needed for a strong version of the Robertson and Seymour’s excluded minor theorem as presented in:

T. Böhme, K. Kawarabayashi, J. Maharry and B. Mohar, Linear connectivity forces large complete bipartite minors, J. Combin. Theory, Ser. B 99 (2009), 557–582.


Keywords


Graph, graph minor, surface, near-embedding, grid minor, excluded minor.

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.118.3dd

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications