function [r, FC]=coloring_backwards(r, FC, Ct, ub, lower_bound)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General description:
%
% This function searches for the highest numbered vertex among v(1), ...,
% v(r-1), say v(i), the recoloring of which might have an influence on the
% coloring of v(r), v(r+1),.... This function is called by graph_coloring.m
%
% See details in:
% M. Kubale and B. Jackowski. "A generalized implicit enumeration algorithm
% for graph coloring." Communications of the ACM, 28:412-418, 1985.
%
% input:
%       r - resumption point from coloring_forwards.m 
%       FC - Feasible colors for vertices
%       Ct - A current coloring (partial or complete, C' in [Kubale])
%       ub - A upper bound on the chromatic number
%       lower_bound - A lower bound on the chromatic number. Equal to the
%                     size of maximum clique 
% output: 
%       r - index of the 'resumption point'.
%       FC - Feasible colors for vertices
%
% Written by: Wei Wang
% Machine Learning for Signal Processing Lab
% University of Maryland, Baltimore County
% 8/21/2007
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

CP=[1:r-1]; % Current predecessors, i.e., the vertices which are not 
            % omitted by the checking process.

while numel(CP)~=lower_bound
   i=max(CP);
   CP(i)=[];
   pos=find(FC(i,:)==Ct(i));
   
   % remove the current color from the feasible set for vertex i.
   t=FC(i,:);
   t(pos)=[];
   FC(i,1:end-1)=t;
   FC(i,end)=0;
   
   if  FC(i,1)~=0 & FC(i,1)~=ub
       r=i; % The feasible color exists, using i to start a new sweep in 
            % the coloring_forwards procedure. 
       return;
   end
end

% none of current predecessors can be recolored. Hence the best coloring so
% far is the optimum solution.
r=lower_bound;

