论文标题
无冲突的色度与无冲突的色度指数
Conflict-free chromatic number vs conflict-free chromatic index
论文作者
论文摘要
如果每个顶点的封闭社区都包含独特的颜色（即在附近仅出现一次的颜色），则给定图形$ G $的顶点着色是无冲突的。这种着色中的最小颜色数是$ g $的无冲突色数，表示为$χ_{cf}（g）$。给定最大程度$δ$的图的最大无冲突色数是多少？ $χ_{cf}（g）\ leqχ（g）\leqΔ+1 $，但由于Glebov，Szabó和Tardos的结果，远非最佳，以及Bhyravarapu，Bhyravarapu，Kalyanasundaram和Mathew，Mathew和Mathew，已知的答案，该答案是$ the $ the $ the $ t $ fel（$ fel）。 我们表明，线图类别中相同问题的答案是$θ\ left（\lnδ\右）$ - 也就是说，在具有最高度$δ$的图形中，无冲突色索引的极值比无冲突的色度数小得多。 $χ_{cf}（g）$的结果也相同，在近规则图的类别中，即具有最低度$δ\ geqαδ$的图形。
A vertex coloring of a given graph $G$ is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e. a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of $G$, denoted $χ_{CF}(G)$. What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree $Δ$? Trivially, $χ_{CF}(G)\leq χ(G)\leq Δ+1$, but it is far from optimal - due to results of Glebov, Szabó and Tardos, and of Bhyravarapu, Kalyanasundaram and Mathew, the answer in known to be $Θ\left(\ln^2Δ\right)$. We show that the answer to the same question in the class of line graphs is $Θ\left(\lnΔ\right)$ - that is, the extremal value of the conflict-free chromatic index among graphs with maximum degree $Δ$ is much smaller than the one for conflict-free chromatic number. The same result for $χ_{CF}(G)$ is also provided in the class of near regular graphs, i.e. graphs with minimum degree $δ\geq αΔ$.
