2
$\begingroup$

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.

$\endgroup$
4

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

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

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