Combinatorics Seminar

When: Sunday, April 22, 10am Where: Schreiber 309 Speaker: Shakhar Smorodinsky, Ben Gurion University Title: On Vertex Ranking of Graphs and its Relatives

Abstract:

Given a graph $G=(V,E)$, a vertex ranking is a numbering (i.e., a coloring) of the vertices such that if $u$ and $v$ get the same color then every simple path between $u$ and $v$ contains a vertex with a higher color. This notion has been studied extensively. In this talk we present and study a more restricted notion where we consider only path's of bounded length. The first non-trivial case is when we only consider paths of length at most two. That is, we are interested in a proper coloring with the additional constraint that if $u$ and $v$ have the same color then for any simple path $uwv$ we have that the color of $w$ is greater than that of $u$. We show asymptotically tight bounds on this chromatic number for some families of graphs.

Joint work with Ilan Karpas.