t t -tone edge coloring of graphs

Hadeel Al Bazzal · 2026

Read t t -tone edge coloring of graphs by Hadeel Al Bazzal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24571.txt.

Introduction

Hadeel Al Bazzal introduces t-tone edge coloring, where every edge gets t distinct colors and edges a distance d apart share fewer than d colors. The t-tone chromatic index is the smallest color count allowing such a coloring. For two tones, she proves six times the maximum degree minus four as an upper bound, improving the vertex analogue. Trees attain exactly twice the maximum degree. Planar graphs obey a bound of at most 41 or three times the degree plus five, whichever is larger.

Catalog record

CREATORHadeel Al Bazzal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44801
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24571

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

t t -tone edge coloring of graphs Hadeel Al Bazzal Abstract In this paper, we introduce the notion of t t -tone edge coloring. A t t -tone edge k k -coloring of a graph G G assigns to each edge of G G a set of t t distinct colors from { 1 , … , k } \{1,\dots,k\} such that any two edges at distance d d share fewer than d d common colors. The t t -tone chromatic index of G G , denoted by τ t ′ ​ ( G ) \tau^{\prime}_{t}(G) , is the minimum integer k k for which G G admits a t t -tone edge k k -coloring. We focus on the case t = 2 t=2 and establish several upper bounds on τ 2 ′ \tau^{\prime}_{2} . In particular, for every graph G G with maximum degree Δ ⁡ ( G ) ≥ 2 \Delta(G)\geq 2 , we prove that τ 2 ′ ​ ( G ) ≤ 6 ​ Δ ​ ( G ) − 4 \tau^{\prime}_{2}(G)\leq 6\Delta(G)-4 , improving the corresponding bound derived from the vertex analogue. We also show that every tree T T with Δ ⁡ ( T ) ≥ 3 \Delta(T)\geq 3 satisfies τ 2 ′ ​ ( T ) = 2 ​ Δ ​ ( T ) \tau^{\prime}_{2}(T)=2\Delta(T) . Furthermore, every planar graph G G satisfies τ 2 ′ ​ ( G ) ≤ max ⁡ { 41 , 3 ​ Δ ​ ( G ) + 5 } \tau^{\prime}_{2}(G)\leq\max\{41,3\Delta(G)+5\} , while every outerplanar graph G G satisfies τ 2 ′ ​ ( G ) ≤ max ⁡ { 14 , 3 ​ Δ ​ ( G ) } \tau^{\prime}_{2}(G)\leq\max\{14,3\Delta(G)\} . For subcubic graphs G G , the vertex analogue yields τ 2 ′ ​ ( G ) ≤ 12 \tau^{\prime}_{2}(G)\leq 12 . We improve this bound to 11 11 for claw-free subcubic graphs and to 10 10 for 2 2 -degenerate subcubic graphs. Finally, we propose two conjectures concerning optimal bounds for cubic and K 4 K_{4} -free cubic graphs, and establish them for series-parallel subcubic multigraphs and subcubic outerplanar graphs, respectively. Keywords: t -tone edge coloring, t -tone chromatic index, subcubic graph, planar graph, series-parallel multigraph, outerplanar graph. AMS Subject Classification: 05C15 1 Introduction Throughout this paper, all graphs are assumed to be simple and finite unless stated otherwise. We denote the vertex set and edge set of a graph G by V(G) and E(G) , respectively. In a proper coloring of a graph G , a color (integer) is assigned to each vertex of G such that adjacent vertices receive distinct colors. The chromatic number of G , denoted by \chi(G) , is the minimum integer k for which G admits a proper coloring. Over time, this classical notion has inspired numerous generalizations. For instance, in a distance- t coloring [ 10 ] , the condition is strengthened so that any two vertices at distance at most t receive distinct colors. Another extension is the notion of a t -tone k -coloring [ 3 , 8 ] . A t -tone k -coloring of a graph G assigns to each vertex of G a set of t distinct colors from \{1,\dots,k\} such that any two vertices at distance d share fewer than d common colors. The minimum integer k for which G admits a t -tone k -coloring is called the t -tone chromatic number of G , denoted by \tau_{t}(G) . Note that the distance between two distinct vertices u and v in G , denoted by d_{G}(u,v) , is the length of a shortest path between u and v in G . Edge analogues of several vertex coloring notions have also been studied. In particular, a proper edge coloring of a graph G assigns colors to each edge of G such that adjacent edges receive distinct colors. The chromatic index of G , denoted by \chi^{\prime}(G) , is the minimum integer k for which G admits a proper edge coloring. Furthermore, a distance- t edge coloring [ 9 ] of a graph G assigns a color to each edge of G such that any two edges at distance at most t receive distinct colors. The distance- t chromatic index of G , denoted by \chi^{\prime}_{t}(G) , is the minimum integer k for which G admits a distance- t edge coloring. This parameter is related to graph powers, since \chi^{\prime}_{t}(G)=\chi((L(G))^{t}) , where L(G) denotes the line graph of G , and G^{t} denotes the t -th power of a graph G , obtained by joining all pairs of vertices at distance at most t . In the context of distance- t edge coloring, the distance between two edges e,e^{\prime}\in E(G) is defined as the distance between the corresponding vertices in the line graph L(G) of G . We adopt the same definition throughout this paper and denote this distance by d_{G}(e,e^{\prime}) . While t -tone coloring has been investigated for vertices, to the best of our knowledge, no edge analogue of this notion has yet been studied. In this paper, we introduce and study the notion of t -tone edge coloring. Definition 1.1 . Let G be a graph and let k,t\in\mathbb{N} with 1\leq t\leq k . Let \binom{\{1,\dots,k\}}{t} denote the set of all t -element subsets of \{1,\ldots,k\} . A t -tone edge k -coloring of G is a mapping f:E(G)\to\binom{\{1,\dots,k\}}{t} such that for any two edges e,e^{\prime}\in E(G) , we have |f(e)\cap f(e^{\prime})|<d_{G}(e,e^{\prime}) . A graph admitting a t -tone edge k -coloring is said to be t -tone edge k -colorable. The t -tone chromatic index of G , denoted by \tau^{\prime}_{t}(G) , is the minimum integer k such that G admits a t -tone edge k -coloring. Given a t -tone edge coloring f of G , we call f(e) the label of e and the elements of \{1,\dots,k\} colors. When no ambiguity arises, we omit set brackets in labels; that is, the label \{a,b\} is written simply as ab . Edges e and e^{\prime} (or vertices x and y ) are considered neighbors when their distance is one, and second neighbors when their distance is two. The degree of a vertex v in G , denoted by d_{G}(v) , is the number of edges incident with v . The maximum vertex degree of G is denoted by \Delta(G) . Similarly, the degree of an edge e of G , denoted by d_{G}(e) , is the number of edges adjacent to e . In particular, if e=xy , then d_{G}(e)=d_{G}(x)+d_{G}(y)-2 . For an edge xy\in E(G) , we also define \eta_{G}(xy)=\left|\bigl(N_{G}(x)\cup N_{G}(y)\bigr)\setminus\{x,y\}\right|=|N_{G}(x)\cup N_{G}(y)|-2. Graph families are denoted by C_{n} , P_{n} , and K_{n} for the cycle, path, and complete graph on n vertices, respectively, and by K_{1,n} for the star on n+1 vertices. Clearly, \tau^{\prime}_{t}(K_{1,n})=tn . The notion of t -tone edge coloring generalizes proper edge coloring. In particular, when t=1 , we obtain \tau^{\prime}_{1}(G)=\chi^{\prime}(G) for every graph G . Note that, for each t , the parameter \tau^{\prime}_{t} is monotone under taking subgraphs: if H is a subgraph of G , then \tau^{\prime}_{t}(H)\leq\tau^{\prime}_{t}(G) . A natural lower bound for \tau^{\prime}_{t}(G) arises from the local obstruction

Read the complete text