- #1

- 5

- 0

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 n

^{1/2}

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

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

Then I tried again.

I know Chi (X) >= n/[tex]\alpha (G)[/tex]

and Chi (X) >= [tex]\omega (G complement)[/tex] = [tex]\alpha (G)[/tex]

So I know Chi(G) >= [tex]\alpha (G complement) [/tex]

and Chi(G complement) >=[tex]\alpha (G) [/tex]

and Now I am totally confused... not sure what to do.

If I could get some help that would be great.

Thanks