Graph 3-colors coloring with the use of the given function

Question

I have the function three_colorability(n,E) which gives output true(when the graph with those edges and vertices can be coloured with 3 colors) or false(if not). (!there is no parameter to know what has been coloured already) We assume that this function works in linear time complexity.

I have to make 3-coloring algorithm of the given undirected graph G with the use of the given function which will work in polynomial time.

I can't come to the solution to this.

Answer 1

Add 3 new nodes, named C1, C2 and C3 by colour they represent. Add edges between new nodes (C1,C2), (C2,C3) and (C1,C3). If three_colorability(V,E) is true than three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) is also true.

For each (original) vertex v, three_colorability() returns true for at least one of graphs with added two edge of {(v,C1), (v,C2), (v,C3)}. E.g. if three_colorability() returns true for graph with added edges {(v,C2), (v,C3)}, it means that v can be coloured with colour 1.

To find colour for all vertices, incrementally find vertex colour and add these 2 edges in a graph.