2012/02/06 by Saieed Akbari, Jaehoon Kim, Akbari, Saieed +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1202.1046
8 pages, 1 figure
arxiv created 2012/02/06 · openalex publication_date 2012/02/06 · arxiv updated 2012/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A harmonious coloring of G is a proper vertex coloring of G such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of G, h(G), is the minimum number of colors needed for a harmonious coloring of G. We show that if T is a forest of order n with maximum degree Δ(T)≥ (n+2)/(3), then h(T)= Δ(T)+2, if T has non-adjacent vertices of degree Δ(T); Δ(T)+1, otherwise. Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest.