Algorithms for Finding Generalized Coloring of Trees

Main Article Content

Tanveer Awal
M. Mahbubuzzaman
MD. Abul Kashem

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.

Article Details

How to Cite
Awal, T., Mahbubuzzaman, M., & Kashem, M. A. (2011). Algorithms for Finding Generalized Coloring of Trees. INFOCOMP Journal of Computer Science, 10(1), 36-44. Retrieved from http://infocomp.dcc.ufla.br/index.php/infocomp/article/view/326
Section
Articles