{
  "id": "1508.03052",
  "version": "v1",
  "published": "2015-08-12T20:08:42.000Z",
  "updated": "2015-08-12T20:08:42.000Z",
  "title": "On the precise value of the strong chromatic-index of a planar graph with a large girth",
  "authors": [
    "Gerard Jennhwa Chang",
    "Guan-Huei Duh"
  ],
  "comment": "11 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A strong $k$-edge-coloring of a graph $G$ is a mapping from $E(G)$ to $\\{1,2,\\ldots,k\\}$ such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic index $\\chi'_s(G)$ of a graph $G$ is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. The concept of strong edge-coloring was introduced by Fouquet and Jolivet to model the channel assignment in some radio networks. Denote $\\sigma(G)=\\max_{xy\\in E(G)}\\{\\operatorname{deg}(x)+\\operatorname{deg}(y)-1\\}$. It is easy to see that $\\sigma(G) \\le \\chi'_s(G)$ for any graph $G$, and the equality holds when $G$ is a tree. For a planar graph $G$ of maximum degree $\\Delta$, it was proved that $\\chi'_s(G) \\le 4 \\Delta +4$ by using the Four Color Theorem. The upper bound was then reduced to $4\\Delta$, $3\\Delta+5$, $3\\Delta+1$, $3\\Delta$, $2\\Delta-1$ under different conditions for $\\Delta$ and the girth. In this paper, we prove that if the girth of a planar graph $G$ is large enough and $\\sigma(G)\\geq \\Delta(G)+2$, then the strong chromatic index of $G$ is precisely $\\sigma(G)$. This result reflects the intuition that a planar graph with a large girth locally looks like a tree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-12T20:08:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "planar graph",
      "precise value",
      "strong chromatic-index",
      "strong chromatic index",
      "large girth locally looks"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}