# Homework Help: Graph Theory

1. Mar 25, 2010

### ak_89

I am working on graph theory assignment. I need help because I am not seeing where I am going with this question.

Here's the question: G is a simple graph with n vertices.

-> show that vertex colouring of G [ X(G) ]* vertex colouring of G complement >= n

-> show that the vertex colouring of G + the vertex colouring of G complement >= 2 n1/2

Here's what I have looked at. I know Chi (G) =< $$\Delta G +1$$ and same with G complement.

$$\Delta G$$ =< n-1. Then I kind of played around with it. Didn't get anywhere.

Then I tried again.

I know Chi (X) >= n/$$\alpha (G)$$
and Chi (X) >= $$\omega (G complement)$$ = $$\alpha (G)$$

So I know Chi(G) >= $$\alpha (G complement)$$
and Chi(G complement) >=$$\alpha (G)$$

and Now I am totally confused... not sure what to do.
If I could get some help that would be great.
Thanks