Abstract:
This thesis presents an efficient algorithm for finding an optimal I-vertex-coloring of a
partial k-tree. An I-vertex-coloring of a graph G is defined as follows: for a positive
integer I and a graph G with non-negative integer weights on edges, a generalized vertexcoloring,
called an I-vertex-coloring of G, is an assigmnent of colors to the vertices of G
in such a way that any two vertices u and v get different colors if the distance between u
and v in G is at most I. A partial k-tree is a graph with tree-width bounded by a fixed
integer k. An I-vertex-coloring is optimal if the number of colors used is as small as
possible. The problem of finding an I-vertex-coloring of G plays an important role in
meeting, examination and class scheduling, 4-coloring of maps with adjacent regions
having different colors, allocation of registers to the CPU, etc. We present an G(n(l +
2)2a(k + l)aloga + n3
) time algorithm to find an I-vertex-coloring of a partial k-tree G,
where n is the number of vertices in G and a is size of the color-set. The previously
• 22(.1:+1)(1+2)+1 3. known best algonthm takes G(n(a + I) + n ) time to find an optimal I-vertexcoloring
of a partial k-tree.
