论文标题
关于无冲突色索引的注释
A note on the conflict-free chromatic index
论文作者
论文摘要
令$ g $为具有最高度$δ$的图形，而没有孤立的顶点。如果每个边缘的封闭社区都包含一个独特的颜色元素，则边缘着色$ c $ $ g $是无冲突的。承认这样的$ c $的最少颜色是$ g $的无冲突色索引，由$χ'_{cf}（g）$表示。在“无冲突的色数与无冲突的色度指数”中[J。图理论，2022； 99：349---358]最近通过概率方法证明了$χ'_{cf}（g）\ leq c_1 \ loq c_1 \log_2Δ+c_2 $，其中$ c_1> 337 $和$ c_2 $和$ c_2 $是常数，而有$χ'_ _ _ {cf}（c）（c） （1-O（1））\log_2Δ$。在本说明中，我们提供了一个明确的简单证明，证明了$χ'_{cf}（g）\ leq 3 \log_2δ+1 $，这是更强结果的推论：$χ'_ {cf}（g）\ leq 3 \log_2χ（g）+1 $。对于此目的，我们证明了一些辅助观察结果，尤其暗示着$χ'_ {cf}（g）\ leq 4 $用于两部分图。
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.
