Evènement pour le groupe GT Graphes et Applications


Date 2016-02-19  14:00-15:00
TitreVertex ranking of a graph 
RésuméA vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P, the maximum color occurring in it is unique in P. The vertex-ranking chromatic-number of G, $chi_{vr}(G)$, is the minimum number of colors for which G has a vertex-ranking. This notion is well documented in the literature, and has some well known practical applications. In this talk we present a relaxation of the vertex ranking notion, a k-vertex ranking. : A k-vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P of length at most k, the maximum color occurring in it is unique in P. Similarly, The k-vertex-ranking chromatic-number of G, $chi_{vr_k}(G)$, is the minimum number of colors with which G can be colored. For planar graphs and minor-free graphs, we show a bound of O(logn) on the k-vertex-ranking chromatic number for k constant. We also provide upper and lower bounds of the 2-vertex-ranking chromatic-number for the families of trees and d-degenerate graphs. We compare our bounds to the bounds already found for the case of ordinary vertex ranking. Joint work with Ofer Neiman and Shakhar Smorodinsky.  
LieuSalle 178 
OrateurIlan Karpas 



Aucun document lié à cet événement.

Retour
Retour à l'index