0

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 2cdot 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 2cdot d(G)-1?

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.