2015/11/19 by Wenjing Li, Xueliang Li, Li, Wenjing +3
Computer Science · Mathematics · #05C15 #05C40 #68Q17 #68Q25 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1511.06119
openalex publication_date 2015/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path in a total-colored graph is called total rainbow if its edges and internal vertices have distinct colors. For an ℓ-connected graph G and an integer k with 1≤ k ≤ℓ, the total rainbow k-connection number of G, denoted by trck(G), is the minimum number of colors used in a total coloring of G to make G total rainbow k-connected, that is, any two vertices of G are connected by k internally vertex-disjoint total rainbow paths. In this paper, we study the computational complexity of total rainbow k-connection number of graphs. We show that it is NP-complete to decide whether trck(G)=3.