2024/09/17 by Shanshan Guo, E. Li, Guo, Shanshan +5
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2409.10899
A graph G is conflict-free k-edge-colorable if there exists an assignment of k colors to E(G) such that for every edge e∈ E(G), there is a color that is assigned to exactly one edge among the closed neighborhood of e. The smallest k such that G is conflict-free k-edge-colorable is called the conflict-free chromatic index of G, denoted χ'CF(G). Dȩbski and Przyby\alo showed that 2≤χ'CF(T)≤ 3 for every tree T of size at least two. In this paper, we present an algorithm to determine the conflict-free chromatic index of a tree without 2-degree vertices, in time O(|V(T)|). This partially answer a question raised by Kamyczura, Meszka and Przyby\alo.