{
  "id": "1803.05085",
  "version": "v1",
  "published": "2018-03-14T00:28:47.000Z",
  "updated": "2018-03-14T00:28:47.000Z",
  "title": "The $\\mathbb{Z}_2$-genus of Kuratowski minors",
  "authors": [
    "Radoslav Fulek",
    "Jan Kynčl"
  ],
  "comment": "21 pages, 5 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 $\\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 $2$ 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-14T00:28:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "57M15",
      "05C83",
      "68R10",
      "15A03"
    ],
    "keywords": [
      "kuratowski minors",
      "sufficiently large genus contains",
      "orientable surface",
      "hanani-tutte theorem",
      "seymour implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}