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.

  • 3
    $\begingroup$ Without more structural information, there could be a clique of size $\Delta+1$, forcing the chromatic number up to $\Delta$. $\endgroup$ – Brendan McKay Jun 12 at 17:17
  • $\begingroup$ @BrendanMcKay what about semi regular graphs, that is, graphs with only two possible numbers in their adjacency list $\endgroup$ – vidyarthi Jun 13 at 8:40
  • 1
    $\begingroup$ 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$. $\endgroup$ – Louis Esperet Jun 13 at 16:04
  • $\begingroup$ @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? $\endgroup$ – vidyarthi Jun 13 at 19:20
  • $\begingroup$ @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? $\endgroup$ – vidyarthi Aug 6 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.