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
> 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.
>
The 4-colour theorem is for planar graphs. A planar graph has O(n)
edges, but not every graph with O(n) edges is planar (for instance,
K_{3, k} with k >= 3).
It's not obvious to me why looking at planar graphs/trees/even
bipartite graphs is enough. My guess is that you are confusing O(|V|)
with |V| (especially when you say a connected graph with O(|V| - 1)
edges is a tree -- the correct statement is a connected graph with |V|
- 1 edges is a tree).
The second response is also incorrect. Suppose $G$ is a k-colourable
graph. Take any k-colouring of G. It is necessarily true that two
vertices that are assigned different colours are connected by an edge.
Returning to the OP's question, take a connected, simple graph G with
O(n) edges -- say at most kn edges, for some constant k (we may assume
without loss of generality that G is simple, otherwise we can simply
delete loops and parallel edges). (we'll do an induction on n). Let v
be a vertex of minimum degree in G. Clearly, the degree of v is a
constant (the average degree is at most 2k). G\v has n-1 vertices and
O(n) = O(n-1) edges, and by induction can be coloured with O(sqrt(n -
1)) = O(sqrt(n)) colours. The vertex v has a constant number of
neighbours, and there are O(sqrt(n)) colours available, therefore at
least one of the O(sqrt(n)) colours is available for v (not assigned
to a neighbour of v). Therefore O(sqrt(n)) colours suffice.
This problem is not interesting if all constants are hidden in the big-
O notation. The problem would be more interesting if (for instance),
you gave an actual value for E(G) and the number of colours.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
