2025/12/11 by Yuping Gao, Gao, Yuping, Songling Shan +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2512.10827
openalex publication_date 2025/12/11 · openalex created_date 2025/12/13 · openalex updated_date 2026/07/28
Let k ≥ 1 be an integer and let G be a nonempty simple graph. An edge-k-coloring φ of G is an assignment of colors from \1,…,k\ to the edges of G such that no two adjacent edges receive the same color. For a vertex v ∈ V(G), we write φ(v) for the set of colors assigned to the edges incident with v. The coloring φ is called vertex-distinguishing if φ(u) ≠ φ(v) for every pair of distinct vertices u,v ∈ V(G). A vertex-distinguishing edge-k-coloring exists if and only if G has at most one isolated vertex and no isolated edge. The least integer k for which such a coloring exists is called the vertex-distinguishing chromatic index of G, denoted χ'vd(G). In 1997, Burris and Schelp conjectured that for every graph G with at most one isolated vertex and no isolated edge, k(G) ≤ χ'vd(G) ≤ k(G)+1, where k(G) is the natural lower bound required for a vertex-distinguishing coloring in G. In 2004, Balister, Kostochka, Li, and Schelp verified the conjecture for graphs G satisfying Δ(G) ≥ √(2|V(G)|) + 4 and δ(G) ≥ 5. For graphs that do not satisfy these conditions, the best known general upper bound on χ'vd(G) remains |V(G)| + 1, established in 1999 by Bazgan, Harkat-Benhamdine, Li, and Woźniak. In this paper, we prove that χ'vd(G) ≤ \floor5.5k(G)+6.5, which represents a substantial improvement over the bound |V(G)| + 1 whenever k(G) = o(|V(G)|). We further show that χ'vd(G) ≤ k(G) + 3, for all d-regular graphs G with d ≥ log2 |V(G)|≥ 8.