Back to Search
Start Over
Partitions of graphs into small and large sets.
- Source :
-
Discrete Applied Mathematics . Sep2013, Vol. 161 Issue 13/14, p1912-1924. 13p. - Publication Year :
- 2013
-
Abstract
- Abstract: Let be a graph on vertices. We call a subset of the vertex set -small if, for every vertex , . A subset is called -large if, for every vertex , . Moreover, we denote by the minimum integer such that there is a partition of into -small sets, and by the minimum integer such that there is a partition of into -large sets. In this paper, we will show tight connections between -small sets, respectively -large sets, and the -independence number, the clique number and the chromatic number of a graph. We shall develop greedy algorithms to compute in linear time both and and prove various sharp inequalities concerning these parameters, which we will use to obtain refinements of the Caro–Wei Theorem, Turán’s Theorem and the Hansen–Zheng Theorem among other things. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 161
- Issue :
- 13/14
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 89105911
- Full Text :
- https://doi.org/10.1016/j.dam.2013.02.038