1
$\begingroup$

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

$\endgroup$
2

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – user17381
    Aug 25, 2011 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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