MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEGrundy number on P4-classes par Julio Araujo
Date : | 19/01/10 | Time : | 10:30 | Location : | Lagrange Gris |
A vertex k-coloring of a graph G = (V,E) is an assignment of k colors to V(G). We say that a vertex k-coloring is a proper if each pair of adjacent vertices receive disjoint colors. Given a graph G, in the Vertex Coloring Problem we want to determine the chromatic number of G, defined as the minimum value k such that G admits a proper k-coloring of its vertices. Determining the chromatic number of a graph is a NP-Hard problem.
The first-fit algorithm for vertex coloring is probably the most famous heuristic to generate proper vertex colorings of a graph. Given a graph G = (V,E) and an order O = v1, . . . , vn over V, the first-fit algorithm assigns to vi the minimum positive integer that was not already assigned to its neighborhood in the set {v1, . . . , v_k}. A coloring obtained by an execution of this algorithm is usually called as greedy. The maximum number of colors of a greedy coloring of a graph G, over all the orders O of V(G), is the Grundy number of G. In the Greedy Coloring Problem we want to determine the Grundy number of a given graph.
In this talk, we will show the definition of a new class of graphs, the fat-extended P4-laden graphs, and also that there is a polynomial time algorithm to determine the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for any graph of the following classes: P4-reducible, extended P4-reducible, P4-sparse, extended P4-sparse, P4-extensible, P4-lite, P4-tidy, P4-laden and extended P4-laden, which are all strictly contained in the fat-extended P4-laden class.
These results were obtained in a joint work with Claudia Linhares Sales
Page des séminaires
|