{
  "id": "1105.1023",
  "version": "v1",
  "published": "2011-05-05T09:41:59.000Z",
  "updated": "2011-05-05T09:41:59.000Z",
  "title": "Vertex coloring of plane graphs with nonrepetitive boundary paths",
  "authors": [
    "János Barát",
    "Július Czap"
  ],
  "journal": "Journal of Graph Theory, 2012",
  "doi": "10.1002/jgt.21695",
  "categories": [
    "math.CO"
  ],
  "abstract": "A sequence $s_1,s_2,...,s_k,s_1,s_2,...,s_k$ is a repetition. A sequence $S$ is nonrepetitive, if no subsequence of consecutive terms of $S$ form a repetition. Let $G$ be a vertex colored graph. A path of $G$ is nonrepetitive, if the sequence of colors on its vertices is nonrepetitive. If $G$ is a plane graph, then a facial nonrepetitive vertex coloring of $G$ is a vertex coloring such that any facial path is nonrepetitive. Let $\\pi_f(G)$ denote the minimum number of colors of a facial nonrepetitive vertex coloring of $G$. Jendro\\vl and Harant posed a conjecture that $\\pi_f(G)$ can be bounded from above by a constant. We prove that $\\pi_f(G)\\le 24$ for any plane graph $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-05T09:41:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "plane graph",
      "nonrepetitive boundary paths",
      "facial nonrepetitive vertex coloring",
      "repetition",
      "vertex colored graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.1023B"
    }
  }
}