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. |