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

  • Context: Graduate 
  • Thread starter Thread starter math8
  • Start date Start date
  • Tags Tags
    Graph Minimum
Click For Summary
SUMMARY

The minimum number of edges in a k-chromatic connected graph of order n is established as \(\binom{k}{2} + n - k\). This conclusion is derived from the properties of the complete graph \(K_k\), which contains \(\binom{k}{2}\) edges. Additionally, it is noted that if the chromatic number \(\chi(M) = k\) and a vertex \(v\) has a degree less than \(k\), the chromatic number remains \(k\) when \(v\) and its edges are added to graph \(M\). Proving Hadwiger's conjecture could simplify this problem further.

PREREQUISITES
  • Understanding of graph theory concepts, particularly chromatic numbers
  • Familiarity with complete graphs, specifically \(K_k\)
  • Knowledge of combinatorial notation, such as binomial coefficients
  • Basic principles of conjectures in mathematics, including Hadwiger's conjecture
NEXT STEPS
  • Research the properties of chromatic numbers in graph theory
  • Study the implications of Hadwiger's conjecture on graph connectivity
  • Explore combinatorial proofs involving binomial coefficients
  • Examine examples of k-chromatic graphs and their edge configurations
USEFUL FOR

Mathematicians, graph theorists, and students studying advanced graph theory concepts, particularly those interested in chromatic numbers and edge configurations in connected graphs.

math8
Messages
143
Reaction score
0
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.
 
Physics news on Phys.org
Did you solve it?

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

HTH
 

Similar threads

MHB Prove the minimum and maximum edges in a graph
  • · Replies 6 ·
Replies
6
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
494
Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
3K
MHB Find total number of republications
  • · Replies 22 ·
Replies
22
Views
2K
MHB Chromatic number vs chromatic index
  • · Replies 8 ·
Replies
8
Views
7K
Undergrad How to calculate expectation and variance of kernel density estimator?
  • · Replies 9 ·
Replies
9
Views
3K
MHB Ice Cream : NP-complete problem
  • · Replies 6 ·
Replies
6
Views
2K