{
  "id": "1508.01266",
  "version": "v1",
  "published": "2015-08-06T02:31:18.000Z",
  "updated": "2015-08-06T02:31:18.000Z",
  "title": "Cartesian Product and Acyclic Edge Colouring",
  "authors": [
    "Rahul Muthu",
    "C. R. Subramanian"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The acyclic chromatic index, denoted by $a'(G)$, of a graph $G$ is the minimum number of colours used in any proper edge colouring of $G$ such that the union of any two colour classes does not contain a cycle, that is, forms a forest. We show that $a'(G\\Box H)\\le a'(G) + a'(H)$ for any two graphs $G$ and $H$ such that $max\\{a'(G), a'(H)\\} > 1$. Here, $G \\Box H$ denotes the cartesian product of $G$ and $H$. This extends a recent result of [15] where tight and constructive bounds on $a'(G)$ were obtained for a class of grid-like graphs which can be expressed as the cartesian product of a number of paths and cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-06T02:31:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cartesian product",
      "acyclic edge colouring",
      "acyclic chromatic index",
      "colour classes",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150801266M"
    }
  }
}