New potential functions for greedy independence and coloring

A potential function f(G) of a finite, simple and undirected graph G = (V, E) is an arbitrary function f(G) : V (G) -> N-0 that assigns a nonnegative integer to every vertex of a graph G. In this paper we define the iterative process of computing the step potential function qG such that q(G)(nu) <= d(G)(nu) for all nu is an element of V (G). We use this function in the development of new Caro-Wei-type and Brooks-type bounds for the independence number alpha(G) and the Grundy number Gamma(G). In particular, we prove that Gamma(G) <= Q(G) + 1, where Q(G) = max{q(G)(nu)vertical bar nu is an element of V(G)} and alpha(G) >= Sigma(nu is an element of V(G)) (q(G)(nu))+1)(-1). This also establishes new bounds for the number of colors used by the algorithm Greedy and the size of an independent set generated by a suitably modified version of the classical algorithm GreedyMAX. (C) 2014 Elsevier B.V. All rights reserved.