3
$\begingroup$

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 ?

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ How about a lower bound for $\chi(G)$ in terms of average degree? OP is mentioning his interest in lower bound in the question. $\endgroup$
    – Cyriac Antony
    Feb 24, 2022 at 3:53
0
$\begingroup$

What about $\text{Chromatic_Number}($G$) = X(G) ≤ 1 + \text{Average_Degree}(G)$,

I can’t think of a counterexample, but can’t prove it either

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Misha Lavrov
    Feb 14, 2019 at 0:14
  • $\begingroup$ @ Misha Lavrov What if G is connected? $\endgroup$
    – robothead
    Dec 3, 2021 at 9:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .