New potential functions for greedy independence and coloring

A potential function fGfG of a finite, simple and undirected graph G=(V,E)G=(V,E) is an arbitrary function fG:V(G)→N0fG:V(G)→N0 that assigns a nonnegative integer to every vertex of a graph GG. In this paper we define the iterative process of computing the step potential function  qGqG such that qG(v)≤dG(v)qG(v)≤dG(v) for all v∈V(G)v∈V(G). We use this function in the development of new Caro–Wei-type and Brooks-type bounds for the independence number α(G)α(G) and the Grundy number Γ(G)Γ(G). In particular, we prove that Γ(G)≤Q(G)+1Γ(G)≤Q(G)+1, where Q(G)=max{qG(v)|v∈V(G)} and α(G)≥∑v∈V(G)(qG(v)+1)−1α(G)≥∑v∈V(G)(qG(v)+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.