Answer to Question #171310 in Combinatorics | Number Theory for Shannon

Question #171310

Let G be a graph on n vertices and G' be the complement of G. Give an argument supporting why the chromatic number of G times the chromatic number of G' is greater than or equal to n.


1
Expert's answer
2021-03-16T08:33:12-0400

Сhromatic number "\\chi(G)" of a graph G is the smallest number of colors needed to color vertices of G so that every two vertices connected by an edge in G have different colors (we name such colorings as valid colorings).

Let "\\chi(G)=k, \\chi(G\u2019)=m, I_k=\\{1,2,\\dots, k\\}, I_m=\\{1,2, \\dots,m\\}" .

Let "\\phi: V(G)\\to I_k, \\psi: V(G)\\to I_m" are valid colorings of G and G’.

Then "(\\phi,\\psi): V(G)\\to I_k\\times I_m" is a valid coloring of the full graph "G\\cup G\u2019" .

Indeed, let "v_1" and "v_2" be two vertices of G.

Then they are connected by the edge "(v_1, v_2)" either in G or in G’.

If "(v_1, v_2)\\in E(G)" then "(\\phi(v_1),\\psi(v_1))\\ne (\\phi(v_2),\\psi(v_2))" as "\\phi(v_1)\\ne \\phi(v_2)".

If "(v_1, v_2)\\in E(G\u2019)" then "(\\phi(v_1),\\psi(v_1))\\ne (\\phi(v_2),\\psi(v_2))" as "\\psi(v_1)\\ne \\psi(v_2)" .

As we have a valid coloring of the full graph "G\\cup G\u2019", the number of used colors must be greater or equal than "\u03c7(G\\cup G\u2019)". But "\\chi(G\\cup G\u2019)=n" , as all n vertices of this graph are connected. On the other hand, we used not greater than "km" colors for a valid coloring of this graph.

Therefore, "km\\geq n" , as required.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS