MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2010 at 19:08
Vertex ranking number is also known as cycle rank; see en.wikipedia.org/wiki/Cycle_rank – David Eppstein Sep 30 2010 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.

Once you have a sparse graph with linear vertex ranking number such as the one above, you can subdivide every edge to make it 2-degenerate without changing the vertex ranking number, if you like. This increases the number of vertices in the graph by a constant factor, so the vertex ranking number remains linear in the new number of vertices. Therefore, even 2-degenerate graphs can have linear vertex ranking number.

-

Sorry, I don't fully understand. What do you know about the vertex ranking chromatic number of the large biconnected component? Is it necessarily big?

-