The Z2 -Genus of Kuratowski minors

Fulek R, Kynčl J. 2022. The Z<inf>2</inf> -Genus of Kuratowski minors. Discrete and Computational Geometry.

Download
No fulltext has been uploaded. References only!

Journal Article | Epub ahead of print | English

Scopus indexed
Author
Fulek, RadoslavISTA ; Kynčl, Jan
Department
Abstract
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 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 two 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 Štefankovič, and giving an approximate version of the Hanani–Tutte theorem on orientable surfaces. We also obtain an analogous result for Euler genus and Euler Z2-genus of graphs.
Publishing Year
Date Published
2022-07-09
Journal Title
Discrete and Computational Geometry
Acknowledgement
We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen, and John Maharry for information about their unpublished results related to Conjecture 3.1. Finally we thank the reviewers for corrections and suggestions for improving the presentation. Supported by Austrian Science Fund (FWF): M2281-N35. Supported by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University project UNCE/SCI/004.
ISSN
eISSN
IST-REx-ID

Cite this

Fulek R, Kynčl J. The Z<inf>2</inf> -Genus of Kuratowski minors. Discrete and Computational Geometry. 2022. doi:10.1007/s00454-022-00412-w
Fulek, R., & Kynčl, J. (2022). The Z<inf>2</inf> -Genus of Kuratowski minors. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w
Fulek, Radoslav, and Jan Kynčl. “The Z<inf>2</Inf> -Genus of Kuratowski Minors.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w.
R. Fulek and J. Kynčl, “The Z<inf>2</inf> -Genus of Kuratowski minors,” Discrete and Computational Geometry. Springer Nature, 2022.
Fulek R, Kynčl J. 2022. The Z<inf>2</inf> -Genus of Kuratowski minors. Discrete and Computational Geometry.
Fulek, Radoslav, and Jan Kynčl. “The Z<inf>2</Inf> -Genus of Kuratowski Minors.” Discrete and Computational Geometry, Springer Nature, 2022, doi:10.1007/s00454-022-00412-w.
Material in ISTA:
Earlier Version

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1803.05085

Search this title in

Google Scholar