{
  "id": "1505.04908",
  "version": "v1",
  "published": "2015-05-19T08:39:51.000Z",
  "updated": "2015-05-19T08:39:51.000Z",
  "title": "On incidence coloring of Cartesian products of graphs",
  "authors": [
    "Petr Gregor",
    "Borut Lužar"
  ],
  "comment": "8 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "An incidence in a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are \\textit{adjacent} if at least one of the following holds: $(i)$ $v = u$, $(ii)$ $e = f$, or $(iii)$ $vu \\in \\{e,f\\}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $\\Delta(G) + 2$ colors are needed for an incidence coloring of any graph $G$. The conjecture is false in general, but the bound holds for many classes of graphs. We prove it for a wide subclass of Cartesian products of graphs. As a corollary, we infer that it holds for hypercubes answering in affirmative a conjecture of Pai et al.~(Pai et al., Incidence coloring of hypercubes, Theor. Comput. Sci. 557 (2014), 59--65).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-19T08:39:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C76"
    ],
    "keywords": [
      "incidence coloring",
      "cartesian products",
      "conjecture",
      "incidences assigning distinct colors",
      "hypercubes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}