We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

The Z2-genus of Kuratowski minors

00:00

Formal Metadata

Title
The Z2-genus of Kuratowski minors
Title of Series
Number of Parts
21
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
A drawing of a graph on a surface is independently even if every pair of independent edges in the drawing crosses an even number of times. The Z2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t×t grid or one of the following so-called t-Kuratowski graphs: K3,t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the Z2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z2-genus, solving a problem posed by Schaefer and \v{S}tefankovi\v{c}, and giving an approximate version of the Hanani-Tutte theorem on surfaces.