Graph Theory

  • Thread starter ak_89
  • Start date
  • #1
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
 

Answers and Replies

Related Threads on Graph Theory

  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
965
Replies
2
Views
2K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
927
Top