The $\mathbb{Z}_2$-genus of Kuratowski minors
| Autor: | Radoslav Fulek, Jan Kynčl |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Mathematics::Algebraic Geometry Computational Theory and Mathematics Discrete Mathematics (cs.DM) 57M15 05C83 68R10 15A03 FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Geometry and Topology Combinatorics (math.CO) Mathematics::Geometric Topology Computer Science - Discrete Mathematics Theoretical Computer Science |
| DOI: | 10.48550/arxiv.1803.05085 |
| Popis: | A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The $\mathbb{Z}_2$-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\times t$ grid or one of the following so-called $t$-Kuratowski graphs: $K_{3,t}$, or $t$ copies of $K_5$ or $K_{3,3}$ sharing at most two common vertices. We show that the $\mathbb{Z}_2$-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 $\mathbb{Z}_2$-genus, solving a problem posed by Schaefer and \v{S}tefankovi\v{c}, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces. We also obtain an analogous result for Euler genus and Euler $\mathbb{Z}_2$-genus of graphs. Comment: 25 pages, 10 figures; minor revision |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|