- 4,662
- 372
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 K_s or blue copy of K_t. show that R(s,t)\le\chi(G), where R(s,t) is ramsey number and \chi(G) is vertex colouring minimum number of G.
Now I thought of proving that (1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))
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); \chi'(L(G)) is the edges colouring index of L(G).
How do I show (1), I am not sure?
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 K_s or blue copy of K_t. show that R(s,t)\le\chi(G), where R(s,t) is ramsey number and \chi(G) is vertex colouring minimum number of G.
Now I thought of proving that (1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))
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); \chi'(L(G)) is the edges colouring index of L(G).
How do I show (1), I am not sure?