# Chromatic Number and Average degree

Is there any relation between average degree of a graph and chromatic number?

Like if an average degree for a graph is 3.4. Can we say that the graph is not 2-colorable? for Number of edges = 17 and vertices are 10.

So my question is can we do prove of this using handshaking lemma min.degree <= 2E/V <= max. degree ? i.e. if my average degree comes say x then chromatic number is greater than or equal to x ?

You can't do very much. Note that the complete bipartite graph $K_{n,n}$ has average degree $n$ yet it is 2-colorable.
I think the "best" bound of this type that one could possibly obtain is by using the inequality $$\chi(G) \leq \frac{1}{2} + \sqrt{2m+\frac{1}{4}},$$ holding for a graph with $m$ edges.
• How about a lower bound for $\chi(G)$ in terms of average degree? OP is mentioning his interest in lower bound in the question. Feb 24, 2022 at 3:53
What about $$\text{Chromatic_Number}($$G$$) = X(G) ≤ 1 + \text{Average_Degree}(G)$$,
• This isn't true: take $K_n$, add $\binom{n-1}{2}$ isolated vertices, and you have a graph with $\binom n2$ vertices total and $\binom n2$ edges. So the average degree is $2$, yet the chromatic number is $n$. Feb 14, 2019 at 0:14