Help Needed: Graph Theory Assignment on Vertex Colouring

[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 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

 

[mighty2000]

Thank you for reaching out for help with your graph theory assignment. It seems like you have made some good progress in your thinking so far, but are stuck on how to approach the problem further. Here are some suggestions that may help you:

1. Try using an example: Sometimes, working through a specific example can help you see the pattern or logic behind a problem. You could try drawing a simple graph with a few vertices and working through the steps to see how the vertex colouring of G and G complement compare.

2. Think about the definitions: Remember that the vertex colouring of a graph is the minimum number of colours needed to colour all the vertices in such a way that no two adjacent vertices have the same colour. Keeping this definition in mind, see if you can apply it to the problem at hand.

3. Consider the relationship between G and G complement: Since G complement is the set of all edges that are not in G, think about how the vertex colouring of G and G complement may relate to each other. Can you use this relationship to prove the statements given in the question?

4. Use mathematical induction: It may be helpful to use mathematical induction to prove these statements. This involves proving the statements for a base case (such as n = 1 or n = 2) and then showing that if the statements hold for n, they also hold for n+1.

I hope these suggestions help you make progress on your assignment. If you are still stuck, don't hesitate to reach out for more help. Good luck!