Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimum number of edges in a graph of order n with chromatic number k

  1. Oct 12, 2011 #1
    What is the minimum number of edges in a [itex]k[/itex]-chromatic connected graph of order [itex]n[/itex]?

    I have read somewhere that this number is equal to [itex]\left(\begin{array}{c} k \\2 \end{array} \right) +n -k [/itex]

    I was thinking about using [itex]K_k[/itex], the complete graph with [itex]k[/itex] vertices. We know that the number of edges in [itex]K_k[/itex] is equal to [itex]\left(\begin{array}{c} k \\2 \end{array} \right)[/itex].

    Also, I wanted to use the fact that if [itex]\chi (M) = k[/itex] i.e. the chromatic number of a graph [itex]M[/itex] is equal to [itex]k[/itex], and if a vertex [itex]v[/itex] has degree strictly less than [itex]k[/itex], then the chromatic number of ( [itex]M[/itex] together with [itex]v[/itex] and its edges) is also equal to [itex]k.[/itex]

    I am not sure how start, I need help organizing my ideas.
     
  2. jcsd
  3. Oct 22, 2011 #2
    Did you solve it?

    One approach could be to prove Hadwiger's conjecture, then it would be an easy corollary.

    HTH
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Minimum number of edges in a graph of order n with chromatic number k
Loading...