# Bounds on vertex ranking

What are the known bounds for the vertex ranking chromatic number of k-degenerate graphs? I know that for planar graphs, which are in particular 5-degenerate, there are both lower and upper bound of the order of sqrt(n).

-
What is the vertex ranking chromatic number? Could you add this to your question? Thanks! – Louigi Addario-Berry Sep 30 '10 at 19:08
Vertex ranking number is also known as cycle rank; see en.wikipedia.org/wiki/Cycle_rank – David Eppstein Sep 30 '10 at 22:32

I think graphs of bounded degeneracy can have linear vertex ranking number. In particular let $G$ be the Cartesian product of a 3-regular expander graph with $K_2$. Then $G$ is 4-regular (and therefore 4-degenerate), but if you delete any sublinear number of vertices then there will always remain one large biconnected component in the remaining graph (just as in the underlying expander graph, if you delete the corresponding set of vertices there will remain one large connected component). Therefore, $G$ has linear cycle rank.