Graphs : Chromatic Number
Not what you're looking for?
Show that the chromatic number of G_1 + G_2 is X(G_1) + X(G_2) for any two graphs G_1 and G_2.
Where X(G)is the Chromatic Number.
defn: X(G) a proper colouring or simply a colouring of the vertices of G is an assignment of colours to the vertices in such a way that adjacent vertices have distinct colours; X(G) is then the minimal number of colours in a (vertex) colouring of G. Thus, for example, X(C_(2k))=2 and X(C_(2k+1))=3
Chromatic number:
The chromatic number of a graph is the minimum number of colours required to colour it.
http://mathworld.wolfram.com/ChromaticNumber.html
http://planetmath.org/encyclopedia/ChromaticNumber.html
Purchase this Solution
Solution Summary
Graphs and chromatic number are investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.
Solution Preview
Proof:
Suppose X(G_1)=m, X(G_2) is n. Now we consider G=G_1+G_2. It means that first we do G_1 union G_2, after that, we make each vertex in G_1 adjacent with each vertex in G_2. In another word, if u is a vertex in G_1, v is a vertex in G_2, ...
Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Probability Quiz
Some questions on probability
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.