{
  "id": "0802.3529",
  "version": "v1",
  "published": "2008-02-24T19:25:04.000Z",
  "updated": "2008-02-24T19:25:04.000Z",
  "title": "A Remark on Triangle-Critical Graphs",
  "authors": [
    "Anders Sune Pedersen"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A connected $k$-chromatic graph $G$ with $k \\geq 3$ is said to be triangle-critical, if every edge of $G$ is contained in an induced triangle of $G$ and the removal of any triangle from $G$ decreases the chromatic number of $G$ by three. B. Toft posed the problem of showing that the complete graphs on more than two vertices are the only triangle-critical graphs. By applying a method of M. Stiebitz [Discrete Math. 64 (1987), 91--93], we answer the problem affirmatively for triangle-critical $k$-chromatic graphs with $k \\leq 6$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-02-24T19:25:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C05"
    ],
    "keywords": [
      "triangle-critical graphs",
      "chromatic graph",
      "chromatic number",
      "discrete math",
      "complete graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0802.3529S"
    }
  }
}