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
| 
