{
  "id": "1611.10239",
  "version": "v1",
  "published": "2016-11-30T16:01:52.000Z",
  "updated": "2016-11-30T16:01:52.000Z",
  "title": "Defective 2-colorings of planar graphs without 4-cycles and 5-cycles",
  "authors": [
    "Pongpat Sittitrai",
    "Kittikorn Nakprasit"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for each positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for each positive integer $k.$ Finally, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4), (3,5),$ and $(2,9).$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-30T16:01:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "G.2.2"
    ],
    "keywords": [
      "positive integer",
      "colorable planar graphs",
      "np-complete"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}