{
  "id": "2407.19362",
  "version": "v1",
  "published": "2024-07-28T01:55:38.000Z",
  "updated": "2024-07-28T01:55:38.000Z",
  "title": "Odd 4-coloring of outerplanar graphs",
  "authors": [
    "Masaki Kashima",
    "Xuding Zhu"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A proper $k$-coloring of $G$ is called an odd coloring of $G$ if for every vertex $v$, there is a color that appears at an odd number of neighbors of $v$. This concept was introduced recently by Petru\\v{s}evski and \\v{S}krekovski, and they conjectured that every planar graph is odd 5-colorable. Towards this conjecture, Caro, Petru\\v{s}evski, and \\v{S}krekovski showed that every outerplanar graph is odd 5-colorable, and this bound is tight since the cycle of length 5 is not odd 4-colorable. Recently, the first author and others showed that every maximal outerplanar graph is odd 4-colorable. In this paper, we show that a connected outerplanar graph $G$ is odd 4-colorable if and only if $G$ contains a block which is not a copy of the cycle of length 5. This strengthens the result by Caro, Petru\\v{s}evski, and \\v{S}krekovski, and gives a complete characterization of odd 4-colorable outerplanar graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-28T01:55:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximal outerplanar graph",
      "odd number",
      "first author",
      "connected outerplanar graph",
      "complete characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}