{
  "id": "2208.07338",
  "version": "v1",
  "published": "2022-08-15T17:08:01.000Z",
  "updated": "2022-08-15T17:08:01.000Z",
  "title": "Every graph with no $\\mathcal{K}_8^{-4}$ minor is $7$-colorable",
  "authors": [
    "Michael Lafferty",
    "Zi-Xia Song"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Hadwiger's Conjecture from 1943 states that every graph with no $K_{t}$ minor is $(t-1)$-colorable; it remains wide open for all $t\\ge 7$. For positive integers $t$ and $s$, let $\\mathcal{K}_t^{-s}$ denote the family of graphs obtained from the complete graph $K_t$ by removing $s$ edges. We say that a graph $G$ has no $\\mathcal{K}_t^{-s}$ minor if it has no $H$ minor for every $H\\in \\mathcal{K}_t^{-s}$. Jakobsen in 1971 proved that every graph with no $\\mathcal{K}_7^{-2}$ minor is $6$-colorable. In this paper we consider the next step and prove that every graph with no $\\mathcal{K}_8^{-4}$ minor is $7$-colorable. Our result implies that $H$-Hadwiger's Conjecture, suggested by Paul Seymour in 2017, is true for every graph $H$ on eight vertices such that the complement of $H$ has maximum degree at least four, a perfect matching, a triangle and a cycle of length four. Our proof utilizes an extremal function for $\\mathcal{K}_8^{-4}$ minors obtained in this paper, generalized Kempe chains of contraction-critical graphs by Rolek and the second author, and the method for finding $K_7$ minors from three different $K_5$ subgraphs by Kawarabayashi and Toft; this method was first developed by Robertson, Seymour and Thomas in 1993 to prove Hadwiger's Conjecture for $t=6$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-15T17:08:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C83"
    ],
    "keywords": [
      "hadwigers conjecture",
      "remains wide open",
      "complete graph",
      "paul seymour",
      "maximum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}