Conflict-free chromatic index of trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917783929880576 |
|---|---|
| author | Guo, Shanshan Li, Ethan Y. H. Li, Luyi Li, Ping |
| author_facet | Guo, Shanshan Li, Ethan Y. H. Li, Luyi Li, Ping |
| contents | 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\in 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\a{l}o showed that $2\leχ'_{CF}(T)\le 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\a{l}o. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10899 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conflict-free chromatic index of trees Guo, Shanshan Li, Ethan Y. H. Li, Luyi Li, Ping Discrete Mathematics Combinatorics 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\in 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\a{l}o showed that $2\leχ'_{CF}(T)\le 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\a{l}o. |
| title | Conflict-free chromatic index of trees |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.10899 |