A Generalized Graph Strict Strong Coloring Algorithm

1. Introduction

The graph coloring is a combinatorial optimization problem. The coloring process is done according to some properties. Let G be a given graph. A proper vertex coloring of a graph is a vertex coloring such that no two adjacent vertices have the same color. The minimum number of colors among all proper colorings of G is its chromatic number χ(G). It is well known that the k-coloring problem for general graphs is NP-complete and the calculation of the chromatic number is NP-hard (Klotz, 2002).

A plenty variety of graph coloring is presented in Chen, Gyarfas, and Schelp (1998). Some others colorings deal with edges of graphs (Caragiannisa, Kaklamanisa, & Persianob, 2002), others with lists (Albertson, Grossman, & Haas, 2000). In addition too, solutions for coloring both vertices and edges of graphs have been proposed (Borodin, Kostochka, & Woodall, 1998).

Often, graph coloring and dominance problems are correlated. Several relations between the chromatic number and some dominance parameters are presented in Chellali and Volkmann (2004).

In Zverovich (2006), a notion of graph strong coloring has been introduced. It defines a dominance relation between graph vertices and color classes. Strong coloring problem has been shown as NP-complete.

After that, in Haddad and Kheddouci (2009), authors defined a strict strong k-coloring (k-SSColoring) of graphs, which is a strong k-coloring with a non-empty constraint on color classes. The new coloring parameters define the dominance property. An exact polynomial time of graph strict strong coloring algorithm for trees has been proposed. Graph Strict Strong Coloring Problem (GSSCP) consists to find the minimum number of colors which check the dominance property for each vertex. In fact, finding exact solutions for general graphs are NP-complete.

As an application of such coloring process we can cite broadcasting (Haddad, Dekar, & Kheddouci, 2008), data dissemination, gossiping.

In this paper, we show that heuristic based algorithms may be a good approach to solve graph strict strong coloring problem for general graphs.

The proposed algorithm is named GGSSCA (Generalized Graph Strict Strong Coloring Algorithm). The complexity of this algorithm is polynomial with respect to the number of vertices. The strict strong chromatic number χ_ss(G) is the minimal number of colors needed to color properly its vertices such that each vertex of G is adjacent to at least one non empty color class (Haddad & Kheddouci, 2009) (Figure 1).

Figure 1.

Example of graph strict strong coloring (adapted from Haddad & Kheddouci, 2009)

The paper is organized as follows: Section 2 gives some preliminary notations and definitions. In Section 3, the proposed algorithm is described. In Section 4, experimental results are presented. In Section 5, the proposed algorithm is applied on trees and results are compared with those of the exact algorithm. Conclusion and future work are given in the last section.

2. Preliminary Defenitions

In this paper, we mean by graph a simple undirected loopless graph with no isolated vertices.

Let G = (V, E) be a graph such that V = {v₁, v₂... v_n} is a finite set of vertices and E ⊆ V × V is a finite set of edges.

Two vertices u and v are neighbors or adjacent if (u, v) ∈ E.

For any u ∈ V, let N (u) = {v ∈ V such that (u, v) ∈ E} be the set of adjacent vertices of u. Let deg (u) = |N (u)| be the degree of the vertex u. A subset of vertex S ⊆ V is said stable or independent if and only if for any vertices u and v of S, (u, v) ∉ E. In other words, elements of S are not adjacent vertices.