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.

  • $\begingroup$ You are asking several questions here, some of which are rather open-ended. $\endgroup$ Commented Oct 14, 2021 at 6:44
  • $\begingroup$ But $d(G)$ can be computed polynomially (dl.acm.org/doi/10.1145/2402.322385). $\endgroup$
    – Dan D-man
    Commented Oct 14, 2021 at 6:53
  • $\begingroup$ Wikipedia lists the relations $a(G) \leq d(G) \leq 2a(G) - 1$. Perhaps you confused $a(G)$ and $d(G)$? $\endgroup$ Commented Oct 14, 2021 at 7:00
  • $\begingroup$ You can find a proof of the upper bound here: orion.math.iastate.edu/butler/PDF/arboricity.pdf. $\endgroup$ Commented Oct 14, 2021 at 7:01

1 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$.


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.