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 , maximal degree , degeneracy , minimal degree , chromatic number .
So ofcourse . Also by definition: . And also .
If we direct each edge to its parents, then . I read that , because the amount of edges is at most . I understand why this is an upper bound to the amount of edges. But why does this imply ?
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.