{
  "id": "2103.06760",
  "version": "v1",
  "published": "2021-03-11T16:15:36.000Z",
  "updated": "2021-03-11T16:15:36.000Z",
  "title": "Toughness, 2-factors and Hamiltonian cycles in $2K_2$-free graphs",
  "authors": [
    "Katsuhiro Ota",
    "Masahiro Sanka"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph $G$ is called a $2K_2$-free graph if it does not contain $2K_2$ as an induced subgraph. In 2014, Broersma et al.\\ showed that every 25-tough $2K_2$-free graph with at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. On the other hand, Kratsch et al.\\ showed that for any $t <\\frac{3}{2}$ there exists a $t$-tough split graph without 2-factors (also, it is a $2K_2$-free graph). In this paper, we present two results. First, we show that every $\\frac{3}{2}$-tough $2K_2$-free graph has a $2$-factor. This result is sharp by the result in split graphs. Second, we show that every 2-tough $2K_2$-free graph is Hamiltonian, which was conjectured by Mou and Pasechnik.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-11T16:15:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38"
    ],
    "keywords": [
      "free graph",
      "hamiltonian cycles",
      "tough split graph",
      "induced subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}