Publications Repository - Gdańsk University of Technology

A potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{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 $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in 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) \leq Q(G) + 1$, where $Q(G) = \max\{q_G(v)\,\vert\,v\in V(G)\}$ and $\alpha(G) \geq \sum_{v\in V(G)}(q_G(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.

Authors

• dr hab. inż. Piotr Borowiecki link open in new tab ,
• Dieter Rautenbach