CODEWITHSUNDEEP
algorithmnp
user3787061
user3787061

Reputation: 61

3-colouring of a graph (polynomial time)?

Can we colour a graph in 3 colours in polynomial time? I read that colouring a graph with 2
colours is easy,but colouring a graph with 3 different colours(No two vertices have the
same color) is np-hard.However,I wonder if there is a magic box that says 'yes' for 'A
graph being 3-colourable in polynomial time?'.If it says 'yes' how would it solve it in
polynomial time? Any Ideas ?

Upvotes: 1

Views: 7286

Answers (2)

kaya3
kaya3

Reputation: 51053

@Peter de Rivaz's answer is probably the simplest one, and uses only O(nk) tests of the "magic box", where k is the number of colours (3 in this question). I was thinking about the problem myself and came up with an alternative solution which is a bit more complex, and uses O(n²) tests of the "magic box", but for the purpose of the proof, it works just as well:

  • Let H be a copy of G.
  • For each pair of vertices u-v where G has no edge u-v:
    • Use the magic box to test if the H the edge u-v is still k-colorable.
    • If it is, add that edge to H. Otherwise, do not add it.
  • Take Hᶜ, the complement of H; it has at most k connected components.
  • Assign colours to each vertex of G based on which component of Hᶜ that vertex is a member of.

This works because after the first stage, H is "edge maximal" in the sense that it is k-colorable but no edge can be added such that it will still be k-colorable. Any graph satisfying this property is necessarily the complement of a graph with at most k connected components, each of which is a complete graph.

  • If Hᶜ has more than k connected components, then choosing a vertex from each component would give a complete subgraph of H on more than k vertices, so H could not be k-colorable. Therefore the algorithm uses at most k colours.
  • Each component of Hᶜ is complete:
    • Consider a k-colouring of H; if this colouring has two vertices of different colours in the same component of Hᶜ, then there must be two such vertices joined by an edge in Hᶜ. That edge could be added to H without breaking the colouring; a contradiction.
    • So in any k-colouring of H, every component of Hᶜ must be monochrome. It follows that any two vertices in the same component of Hᶜ must be connected by an edge in Hᶜ, because having the same colour in all colourings of H, they cannot be connected by an edge in H.
    • Therefore, the algorithm does not colour any adjacent vertices of H the same colour, and hence it does not colour any adjacent vertices of G the same colour because G is a subgraph of H.

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Add 3 new vertices to your graph called red/green/blue, each connected to the other 2 but nothing else.

Then for each vertex in your graph:

  1. Connect the vertex to red and green if the resulting graph is 3 colourable
  2. Otherwise, connect the vertex to green and blue if the resulting graph is 3 colourable
  3. Otherwise, connect the vertex to red and blue (by construction the resulting graph must be 3 colourable)

At the end of this process you will have identified a colour for each vertex (the colour that it is not connected to).

This is O(N*magic) where magic is the complexity of your magic box.

Upvotes: 3

Related Questions