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).
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|
||||||||
|
|
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. |
|||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
0
|
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? |
||
|
|
