{
  "id": "1907.01720",
  "version": "v1",
  "published": "2019-07-03T03:06:17.000Z",
  "updated": "2019-07-03T03:06:17.000Z",
  "title": "Clique immersions and independence number",
  "authors": [
    "Sebastián Bustamante",
    "Daniel A. Quiroz",
    "Maya Stein",
    "José Zamora"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "The analogue of Hadwiger's conjecture for the immersion order states that every graph $G$ contains $K_{\\chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $\\alpha$ contains $K_{\\lceil \\frac n\\alpha\\rceil}$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $\\bigl\\lceil \\frac{\\chi (G)-4}{3.54}\\bigr\\rceil$ vertices. Their result implies that every $n$-vertex graph with independence number $\\alpha$ contains an immersion of a clique on $\\bigl\\lceil \\frac{n}{3.54\\alpha}-1.13\\bigr\\rceil$ vertices. We improve on this result for all $\\alpha\\ge 3$, by showing that every $n$-vertex graph with independence number $\\alpha\\ge 3$ contains an immersion of a clique on $\\bigl\\lfloor \\frac {4n}{9 (\\alpha -1)} \\bigr\\rfloor - \\lfloor \\frac{\\alpha}2 \\rfloor$ vertices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-07-03T03:06:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independence number",
      "clique immersions",
      "vertex graph",
      "immersion order states",
      "result implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}