{
  "id": "2205.15189",
  "version": "v1",
  "published": "2022-05-30T15:43:27.000Z",
  "updated": "2022-05-30T15:43:27.000Z",
  "title": "Independence number of intersection graphs of axis-parallel segments",
  "authors": [
    "Marco Caoduro",
    "Jana Cslovjecsek",
    "Michał Pilipczuk",
    "Karol Węgrzycki"
  ],
  "comment": "10 pages and 3 figures",
  "categories": [
    "math.CO",
    "cs.CG",
    "cs.DM"
  ],
  "abstract": "We prove that for any triangle-free intersection graph of $n$ axis-parallel segments in the plane, the independence number $\\alpha$ of this graph is at least $\\alpha \\ge n/4 + \\Omega(\\sqrt{n})$. We complement this with a construction of a graph in this class satisfying $\\alpha \\le n/4 + c \\sqrt{n}$ for an absolute constant $c$, which demonstrates the optimality of our result.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-05-30T15:43:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C15",
      "05B40",
      "90C27",
      "68W25",
      "G.2.2",
      "G.2.1"
    ],
    "keywords": [
      "axis-parallel segments",
      "independence number",
      "triangle-free intersection graph",
      "absolute constant",
      "complement"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}