Ramsey Number.

  • #1
MathematicalPhysicist
Gold Member
4,189
168

Main Question or Discussion Point

I have this next question which I am trying to resolve.
Let G=(V,E) be some graph (usually in this context threre aren't loops nor directed edges),assume that every red-blue colouring of the edges of G contains a red copy of [tex]K_s[/tex] or blue copy of [tex]K_t[/tex]. show that [tex] R(s,t)\le\chi(G) [/tex], where R(s,t) is ramsey number and [tex]\chi(G)[/tex] is vertex colouring minimum number of G.

Now I thought of proving that [tex](1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))[/tex]
where L(G) is the graph in which you identify each edge of G as a vertex and each vertex in G which is common with two edges in G as an edge in L(G); [tex]\chi'(L(G))[/tex] is the edges colouring index of L(G).
How do I show (1), I am not sure?
 

Answers and Replies

  • #2
MathematicalPhysicist
Gold Member
4,189
168
I forgot to say that if I prove (1), then by Szkres-Erdos I am done.
 
  • #3
525
5
Consider a vertex colouring of G with n=Chi(G) colours and take any red-blue edge colouring of K_n. If an edge in G has end-vertices coloured i and j, colour it the same as the edge ij in K_n. G must contain either blue K_s or red K_t with distinctly coloured vertices and hence K_n must contain either a blue K_s or red K_t, so Chi(G)>=R(s,t).
 
  • #4
MathematicalPhysicist
Gold Member
4,189
168
Thanks.

Easy than I thought it would be.
 

Related Threads for: Ramsey Number.

  • Last Post
Replies
0
Views
830
Replies
6
Views
889
Top