2016/03/25 by Hong Chang, Xueliang Li, Chang, Hong +3
Computer Science · Mathematics · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1603.07840
18 pages
openalex publication_date 2016/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A tree T in an edge-colored graph is a \it proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be a fixed integer with 2≤ k≤ n. For a vertex subset S ⊆ V(G) with |S| ≥ 2, a tree containing all the vertices of S in G is called an S-tree. An edge-coloring of G is called a k-proper coloring if for every k-subset S of V(G), there exists a proper S-tree in G. For a connected graph G, the k-proper index of G, denoted by pxk(G), is the smallest number of colors that are needed in a k-proper coloring of G. In this paper, we show that for every connected graph G of order n and minimum degree δ≥ 3, px3(G)≤ n(ln(δ+1))/(δ+1)(1+oδ(1))+2. We also prove that for every connected graph G with minimum degree at least 3, px3(G) ≤ px3(G[D])+3 when D is a connected 3-way dominating set of G and px3(G) ≤ px3(G[D])+1 when D is a connected 3-dominating set of G. In addition, we obtain tight upper bounds of the 3-proper index for two special graph classes: threshold graphs and chain graphs. Finally, we prove that px3(G) ≤ \lfloor(n)/(2)\rfloor for any 2-connected graphs with at least four vertices.