On Oct 24, 3:25 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> 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
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
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
