Algorithms for Finding Generalized Coloring of Trees

Abstract

Let � be a positive integer, and � be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an �-vertex-coloring of �, is an assignment of colors to the vertices in such a way that any two vertices � and � get different colors if the distance between � and � in � is at most �. A coloring is optimal if it usesminimumnumber of distinct colors. The �-vertex-coloring problem is to find an optimal �-vertex-coloring of a graph �. In this paper we present an ���� � ������ time algorithm to find an �-vertex-coloring of a tree � , where � is the maximum degree of � . The algorithm takes ����� time if both � and � are bounded integers. We compute the upper bound of colors to be � � ������������� ����� . We also present an ���� � ������ time algorithm for solving the �-edge-coloring problem of trees. If both � and � are bounded integers, this algorithm also takes ����� time.