- #1
ak_89
- 5
- 0
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) =< [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
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) =< [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