^{1}

^{2}

^{3}

^{4}

Let C be a set of colors, and let be an integer cost assigned to a color c in C. An edge-coloring of a graph is assigning a color in C to each edge so that any two edges having end-vertex in common have different colors. The cost of an edge-coloring f of G is the sum of costs of colors assigned to all edges e in G. An edge-coloring f of G is optimal if is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.

Let

edge-coloring problem is to find an optimal edge-coloring of G, that is, an edge-coloring f such that

is minimum among all edge-colorings of G. An optimal edge-coloring does not always use the minimum number

using

The cost edge-coloring problem has a natural application for scheduling [

The cost edge-coloring problem is APX-hard even for bipartite graphs [

In this section, we define some basic terms.

Let

Let C be a set of colors. An edge-coloring

index i,

An edge-coloring f of G is called an optimal one if

Let f be an edge-coloring of a graph G. For each vertex v of G, let

We say that a color

In this section we prove the following theorem.

Theorem 1. An optimal edge-coloring of a cactus can be found in polynomial time.

As a proof of Theorem 1, we give a dynamic programming algorithm in the remainder of this section to compute the minimum cost

A dynamic programming method is a standard one to solve a combinatorial problem on graphs with tree- construction. We also use it, and compute the minimum cost

Let b be a node of T with its parent

If

We compute the values

Our algorithm computes

and it can be computed in polynomial time. Thus the remainder problem is how to compute all the values

In this subsection, we explain how to compute all the values

In this case, the block b is either an edge or a cycle. Therefore we have the following two cases to consider.

Case 1: the block b is an edge.

In this case, clearly

and all the values

Case 2: the block b is a cycle.

In this case, we describe the following algorithm to compute

In order to compute

Let

We show how to compute the all the values

We first introduce

The minimum cost maximum flow problem can be solved in time polynomial in the size of the graph [

We are now ready to compute

Case 1: the block b is an edge

Let

and it can be computed in time polynomial in the size of

Case 2: the block b is a cycle.

In this case, let

for each j,

Therefore it suffices to show how to compute

By Equation (1) we have

and hence

In this paper, we show that the cost edge-coloring problem for a cactus G can be solved in polynomial time. It is still open to solve the problem in polynomial time for outerplanar graphs.

This work is partially supported by grants of the thousand talent plan of Zhejiang province.

Zhiqian Ye,Yiming Li,Huiqiang Lu,Xiao Zhou, (2015) Cost Edge-Coloring of a Cactus. World Journal of Engineering and Technology,03,119-134. doi: 10.4236/wjet.2015.33C018