{
  "id": "1202.0667",
  "version": "v2",
  "published": "2012-02-03T11:26:52.000Z",
  "updated": "2012-02-06T10:04:43.000Z",
  "title": "Additive colorings of planar graphs",
  "authors": [
    "Tomasz Bartnicki",
    "Bartłomiej Bosek",
    "Sebastian Czerwiński",
    "Jarosław Grytczuk",
    "Grzegorz Matecki",
    "Wiktor Żelazny"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An \\emph{additive coloring} of a graph $G$ is an assignment of positive integers $\\{1,2,...,k\\}$ to the vertices of $G$ such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number $k$ for which there exists an additive coloring of $G$ is denoted by $\\eta (G)$. We prove that $\\eta (G)\\leqslant 468$ for every planar graph $G$. This improves a previous bound $\\eta (G)\\leqslant 5544$ due to Norin. The proof uses Combinatorial Nullstellensatz and coloring number of planar hypergrahs. We also demonstrate that $\\eta (G)\\leqslant 36$ for 3-colorable planar graphs, and $\\eta (G)\\leqslant 4$ for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each $r\\geqslant 2$ there is an $r$-chromatic graph $G_{r}$ with no additive coloring by elements of any Abelian group of order $r$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-02-06T10:04:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "planar graph",
      "additive coloring",
      "group theoretic version",
      "adjacent vertices",
      "combinatorial nullstellensatz"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.0667B"
    }
  }
}