Algorithms for Finding Generalized Coloring of Trees - Awal, Tanveer; Mahbubuzzaman, M.; Kashem, MD. Abul (INFOCOMP Journal of Computer Science, 2011)
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.