1999/04/26 by Tao Jiang, Douglas B. West, Jiang, Tao +1
Computer Science · Mathematics · #05C35 #05C55 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C35 #msc:05C55
paper · pdf · doi:10.48550/arxiv.math/9904140
5 pages, 1 figure
arxiv created 1999/04/26 · openalex publication_date 1999/04/26 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength is the minimum number of colors needed to achieve the chromatic sum. We construct for each positive integer k a tree with strength k that has maximum degree only 2k-2. The result is best possible.