Wyszukiwarka
Abstrakt
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.
Cytowania
-
6
CrossRef
-
0
Web of Science
-
7
Scopus
Autorzy (2)
-
Dieter Rautenbach
- Universitaet Ulm, Germany Institut fuer Optimierung und Operations Research
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.12.011
- Licencja
- Copyright (2014 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 182,
strony 61 - 72,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Borowiecki P., Rautenbach D.: New potential functions for greedy independence and coloring// DISCRETE APPLIED MATHEMATICS. -Vol. 182, (2015), s.61-72
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.12.011
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 180 razy