A note on the conflict-free chromatic index

Let $G$ be a graph with maximum degree $Δ$ 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 $χ'_{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 $χ'_{CF}(G)\leq C_1\log_2Δ+C_2$, where $C_1>337$ and $C_2$ are constants, whereas there are families of graphs with $χ'_{CF}(G)\geq (1-o(1))\log_2Δ$. In this note we provide an explicit simple proof of the fact that $χ'_{CF}(G)\leq 3\log_2Δ+1$, which is a corollary of a stronger result: $χ'_{CF}(G)\leq 3\log_2χ(G)+1$. For this aim we prove a few auxiliary observations, implying in particular that $χ'_{CF}(G)\leq 4$ for bipartite graphs.

No reviews yet.

No comments yet.