Search
Abstract
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.
Citations
-
6
CrossRef
-
0
Web of Science
-
7
Scopus
Authors (2)
-
Dieter Rautenbach
- Universitaet Ulm, Germany Institut fuer Optimierung und Operations Research
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.12.011
- License
- Copyright (2014 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 182,
pages 61 - 72,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- Borowiecki P., Rautenbach D.: New potential functions for greedy independence and coloring// DISCRETE APPLIED MATHEMATICS. -Vol. 182, (2015), s.61-72
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.12.011
- Verified by:
- Gdańsk University of Technology
seen 180 times