Question

Intro to graph theory question:

1) Draw a graph G with w(G) = 2 (w(g) is clique number) and x(G) = 5 (x(g) is chromatic number)

Answer 1

Given That

* If the vertices of a graph represent academic classes, and two vertices are adjacent if the corresponding classes have people in common, then a coloring of the vertices can be used to schedule class meetings. Here the colors would be schedule times, such as 8MWF, 9MWF, 11TTh, etc.

The chromatic number of a graph W(G) is the minimum number of colors required in a proper coloring; it is denoted W(. The independence number of W(G)

• The natural first question about these graphical parameters is: how small or large can they be in a graph G with nn vertices

that the limits are all attainable: A graph with no edges has chromatic number 1 and independence number nn, while a complete graph has chromatic number nn and independence number 1. These inequalities are thus not very interesting. We will see some that are more interesting.