The color cost of a caterpillar (Q1377806)

Using the positive integers as colours, the cost of a given vertex colouring of a graph is the sum of its colours. The colour cost of a graph is the smallest cost of any proper colouring of the graph. In this paper a fast algorithm is developed for calculating the colour cost of a caterpillar (that is, a tree whose square is Hamiltonian).