On the relation between several graph parameters

Question

Recently, I came across several parameters of graphs. So I know in general graphs, it might be hard to compare between them, but I'd like to try and see which upper/lower bounds can be made.

Some parameters are: arboricity $a(G)$, maximal degree $\Delta(G)$, degeneracy $d(G)$, minimal degree $\delta(G)$, chromatic number $\chi(G)$.

So ofcourse $\delta(G) \leq \Delta(G)$. Also by definition: $d(G)\leq \Delta(G)$. And also $\chi(G) \leq d(G)$.

If we direct each edge to its parents, then $d(G) \leq a(G)$. I read that $a(G) \leq 2\cdot d(G)-1$, because the amount of edges is at most $(|V|-1)\cdot a(G)$. I understand why this is an upper bound to the amount of edges. But why does this imply $a(G) \leq 2\cdot d(G)-1$?

And apart from being smaller than the arboricity, can we bound the pseudoarboricity?

Also, if there are any more inequalities or bounds that can be made using these parameters, I'd be interested to know.

And if there are bounds which require the use of additional parameters, this is also interesting to me.

Answer 1

Your post asks several questions. I will only answer the first one, why $d(G) \leq 2a(G) - 1$, following the exposition in notes of Steven Butler.

As you mention, a graph of arboricity $a(G)$ contains at most $(|V|-1) a(G)$ many edges, and so the average degree is at most $\frac{2(|V|-1) a(G)}{|V|} < 2a(G)$. Consequently, there is a vertex whose degree is $2a(G) - 1$. Since the arboricity of a subgraph of $G$ is always at most $a(G)$, every subgraph of $G$ has a vertex of degree at most $2a(G) - 1$.