Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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

1 Answer 1

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.

share|improve this answer
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? –  user17381 Aug 25 '11 at 13:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.