In fact, we could use only 3 colors to do this, if this graph is connected.
At first, I guess you know the famous 4-color theorem, so 4 colors is enough. In fact, if this graph can be disconnected, then we have to use 4 colors. But if it is connected, then it is a tree plus one extra edge, which makes it an almost tree, except for one cycle. If a connected graph has O(|V|-1) edges, then it is a tree. A tree could be colored in 2 colors: Suppose the root use color red, then the next level would use green, and the next next level would use red ...... Two colors is OK. Then we add one edge into this tree, this would possiblly cause the two endpoints violate the coloring. So we could just add one color, then it is OK. So, 3 color is good. On Oct 21, 9:29 pm, "[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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
