The color cost of a caterpillar

✍ Scribed by Mario Gionfriddo; Frank Harary; Zsolt Tuza

• Book ID: 104113818
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 277 KB
• Volume: 174
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00325-1

✦ Synopsis

Using the positive integers as colors, the cost of a given coloring of the nodes of a graph G is the sum of its colors. The color cost of G is then the smallest cost of any proper coloring of G. We specify three types of caterpillar using their codes. These specifications enable the representation of an arbitrary caterpillar as a sequence of these types. The representation is utilized to develop a fast algorithm for calculating the color cost of a given caterpillar.