Abstract:In this paper, we introduce the notion of $t$-tone edge coloring. A $t$-tone edge $k$-coloring of a graph $G$ assigns to each edge of $G$ a set of $t$ distinct colors from $\{1,\dots,k\}$ such that any two edges at distance $d$ share fewer than $d$ common colors. The $t$-tone chromatic index of $G$, denoted by $\tau'_t(G)$, is the minimum integer $k$ for which $G$ admits a $t$-tone edge $k$-coloring. We focus on the case $t=2$ and establish several upper bounds on $\tau'_2$. In particular, for every graph $G$ with maximum degree $\Delta(G)\ge2$, we prove that $\tau'_2(G)\le 6\Delta(G)-4$, improving the corresponding bound derived from the vertex analogue. We also show that every tree $T$ with $\Delta(T)\ge3$ satisfies $\tau'_2(T)=2\Delta(T)$. Furthermore, every planar graph $G$ satisfies $\tau'_2(G)\le \max\{41,3\Delta(G)+5\}$, while every outerplanar graph $G$ satisfies $\tau'_2(G)\le \max\{14,3\Delta(G)\}$. For subcubic graphs $G$, the vertex analogue yields $\tau'_2(G)\le12$. We improve this bound to $11$ for claw-free subcubic graphs and to $10$ for $2$-degenerate subcubic graphs. Finally, we propose two conjectures concerning optimal bounds for cubic and $K_4$-free cubic graphs, and establish them for series-parallel subcubic multigraphs and subcubic outerplanar graphs, respectively.
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.24571 [math.CO] |
| (or arXiv:2605.24571v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24571 arXiv-issued DOI via DataCite (pending registration) |
From: Hadeel Al Bazzal [view email]
[v1]
Sat, 23 May 2026 13:19:11 UTC (14 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。