0
$\begingroup$

Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have?

My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}: \frac{k(k-1)}{2} \leq m\}$, but I can't prove this.

(This is motivated by the fact that the largest complete graph you can form with $m$ edges has $r(m)$ points.)

$\endgroup$

1 Answer 1

3
$\begingroup$

Your guess is correct. Denote $\chi(G)=k$. Then $G$ contains a subgraph with all degrees at least $k$ (proof: if degree of vertex $v$ is less than $k$, then $\chi(G\setminus v)=k$. Indeed, if $\chi(G\setminus v)<k$, color $G\setminus v$ with $k-1$ colors and then extend this coloring to $v$. So, minimal subgraph of $G$ with chromatic number $k$ can not have vertices of degree less than $k$.) Clearly it has at least $k+1$ vertices, thus at least $k(k+1)/2$ edges.

$\endgroup$

Your Answer

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

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