Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory

  1. Mar 25, 2010 #1
    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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted