function [C,idxVsubG] = JCSD_graph_coloring(G)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function performs an exact graph coloring.
% 
% input:
%       G(n,n) - The whole graph. If G(i,j)=1, then (i,j) is an edge in G
% output: 
%       C(n,1) - Color array. C(i) is the color of the i-th vertex
%       idxVsubG - Indices of colored subgraph
%
% Algorithm description:
% The main part of the algorithm is a combination of the work by: 
% O. Coudert, "Exact coloring of real-life graphs is easy", 34th Design
% Automation Conference, pp. 21 --126, June 1997,
% and  
% M. Kubale and B. Jackowski. "A generalized implicit enumeration algorithm
% for graph coloring." Communications of the ACM, 28:412-418, 1985.
%
% The algorithm consist of 5 steps.
% 1. Find a maximum clique in graph G to obtain the lower bound of chromatic
%    number, and also to reduce graph by removing vertices whose degree is 
%    less than lower bound.
% 2. Preorder graph using a greedy largest first (GLF) algorithm
% 3. Find an initial coloring solution using Dsatur heuristic algorithm to
%    to obtain a upper bound of chromatic number. 
% 4. Loop over graph using Brown's backtracking coloring algorithm
% 5. Restore the original graph 
%
% Written by: Wei Wang
% 8/21/2007
%
% Copyright(c) 2007 by
% Machine Learning for Signal Processing Laboratory
% University of Maryland, Baltimore County
%
% Permission to use, copy, modify, and distribute this software for any
% purpose without fee is hereby granted, provided that this entire notice
% is included in all copies of any software which is or includes a copy
% or modification of this software and in all copies of the supporting
% documentation for such software.
% THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
% WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR DOES NOT MAKE ANY
% REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
% OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Gall=G; 

% Order G such that the degrees of vertices are decreasing
degG=sum(G);
[nG,idxV1]=sort(degG,'descend');
G=G(idxV1,idxV1);

%
% 1. Find a maximum clique in G
%
n=size(G,1);
V=[1:n];
MaxClique = MaxCliqueRec(G, V,[],[],n+2); % find maximum clique in Gall
lower_bound= numel(MaxClique);

% Remove those vertices with degree less than lowerbound since they can be
% easily colored after coloring the rest difficult part.
degG=sum(G);
vdeg_less_lb=find(degG<lower_bound);
vdeg_less_lb=vdeg_less_lb(find(vdeg_less_lb>max(MaxClique)));
tpos=[1:n];
tpos(vdeg_less_lb)=[];
G=G(tpos,tpos);
n=size(G,1);

%
% 2. Preorder graph using a greedy largest first (GLF) algorithm
%
[G, idxV2]=preorder_by_GLF(G,MaxClique);
%idxV=idxV1([idxV2 vdeg_less_lb]);
idxVsubG=idxV1(idxV2); % indices of colored subgraph

%
% 3. Find an initial coloring solution using Dsatur heuristic algorithm
%
Col_initial=coloring_Dsatur(G);
upper_bound=max(Col_initial);

% If upper_bound equal to lower_bound, then this coloring solution is
% an optimum solution, return.
if upper_bound==lower_bound    
    C=Col_initial;  
%     disp('Partitioning results:');
%     disp(C);
    return;
end

%
% 4. Loop over graph using Brown's backtracking coloring algorithm
%
ub=upper_bound+1;  % A upper bound on the chromatic number
last_ub=upper_bound+10; % The previous upper bound
FC=zeros(n,upper_bound); % Feasible colors for vertices
r=lower_bound+1; % The starting point of coloring
C=zeros(n,1); % The best coloring solution so far
Ct=zeros(n,1); % A current coloring (partial or complete, C' in [Kubale])
Ct(1:lower_bound)=[1:lower_bound]; % Coloring Ct with maximum clique

count=1;
while 1
    count=count+1;
    if mod(count,100)==0
        disp(strcat('number of backtracking in partitioning = ', int2str(count)));
    end
    
    % Coloring forwards 
    [r,ub, FC, last_ub, Ct, C]...
        = coloring_forwards(r, G, C, Ct, FC, ub, last_ub, lower_bound);
    if ub==lower_bound
        break;
    end
   
    % Backtracking 
    [r, FC]=coloring_backwards(r, FC, Ct, ub, lower_bound);
    if r==lower_bound
        break;
    end
end
    
%
