Say the graph can be colored with minimum k different color. Then there exists at least one edge between every pair of different colored vertex group. So E>=k*(k-1)/2 ==> k < O(sqrt(E)) = O (V^1/2)
On 10/22/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > > Hi, > > Can some provide me hint or solution to the following problem. > > If a graph has O(|V|) edges , then show that it can be colored > with (O|V| ^ 1/2) colors. > > Thanks > > > > > -- Hongcheng Zhu --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
