{
  "id": "2203.02040",
  "version": "v1",
  "published": "2022-03-03T22:25:03.000Z",
  "updated": "2022-03-03T22:25:03.000Z",
  "title": "A note on the conflict-free chromatic index",
  "authors": [
    "Mateusz Kamyczura",
    "Mariusz Meszka",
    "Jakub Przybyło"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph with maximum degree $\\Delta$ and without isolated vertices. An edge colouring $c$ of $G$ is conflict-free if the closed neighbourhood of every edge includes a uniquely coloured element. The least number of colours admitting such $c$ is the conflict-free chromatic index of $G$, denoted by $\\chi'_{CF}(G)$. In \"Conflict-free chromatic number versus conflict-free chromatic index\" [J. Graph Theory, 2022; 99: 349--358] it was recently proved by means of the probabilistic method that $\\chi'_{CF}(G)\\leq C_1\\log_2\\Delta+C_2$, where $C_1>337$ and $C_2$ are constants, whereas there are families of graphs with $\\chi'_{CF}(G)\\geq (1-o(1))\\log_2\\Delta$. In this note we provide an explicit simple proof of the fact that $\\chi'_{CF}(G)\\leq 3\\log_2\\Delta+1$, which is a corollary of a stronger result: $\\chi'_{CF}(G)\\leq 3\\log_2\\chi(G)+1$. For this aim we prove a few auxiliary observations, implying in particular that $\\chi'_{CF}(G)\\leq 4$ for bipartite graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-03-03T22:25:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "conflict-free chromatic index",
      "explicit simple proof",
      "conflict-free chromatic number",
      "stronger result",
      "bipartite graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}