# Bounds on chromatic number when maximum degree is large

For a regular graph with $$n$$ vertices and maximum degree $$\Delta$$, it is easy to see that the chromatic number, $$\chi\le\frac{n}{2}$$ if $$\frac{n}{2}\le\Delta\lt n-1$$(since a regular graph on $$n$$ vertices with maximum degree $$n-2$$ is the complete graph with a one factor removed, which will have each vertex non adjacent to a unique other vertex, which could be given the same color, using the handshaking lemma we get that chromatic number of such a graph is $$\frac{n}{2}$$)

How could this fact be applied to bound the chromatic number of any non-regular graph with large maximum degree. Does this fact have a well known name, like Reed's theorem, or Brooks' theorem? Thanks beforehand.

• Without more structural information, there could be a clique of size $\Delta+1$, forcing the chromatic number up to $\Delta$. – Brendan McKay Jun 12 at 17:17
• @BrendanMcKay what about semi regular graphs, that is, graphs with only two possible numbers in their adjacency list – vidyarthi Jun 13 at 8:40
• By the way @vidyarthi I'm afraid your proof only works when $\Delta=n-2$, ie when the complement is a perfect matching. For instance, take your graph to be the complement of a k-regular graph with no triangle and no perfect matching. Then the graph is $(n-k-1)$-regular, and $\chi>n/2$. – Louis Esperet Jun 13 at 16:04
• @LouisEsperet thanks! so this shows that my claim is false. But, then, the next question is, how large the $\chi$ can be? Is there an upper bound? – vidyarthi Jun 13 at 19:20
• @LouisEsperet By Dirac's theorem, a graph with $\Delta\ge \frac{n}{2}$ has a hamiltonian cycle. So, if the graph be of even order, then there will always exist a perfect matching right? – vidyarthi Aug 6 at 12:13