2012/05/08 by Asen Bojilov, Yair Caro, Bojilov, Asen +5
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1205.1727
21 pages
arxiv created 2012/05/08 · arxiv updated 2012/05/09
Let G be a graph on n vertices. We call a subset A of the vertex set V(G) k-small if, for every vertex v ∈ A, °(v) ≤ n - |A| + k. A subset B ⊆ V(G) is called k-large if, for every vertex u ∈ B, °(u) ≥ |B| - k - 1. Moreover, we denote by φk(G) the minimum integer t such that there is a partition of V(G) into t k-small sets, and by Ωk(G) the minimum integer t such that there is a partition of V(G) into t k-large sets. In this paper, we will show tight connections between k-small sets, respectively k-large sets, and the k-independence number, the clique number and the chromatic number of a graph. We shall develop greedy algorithms to compute in linear time both φk(G) and Ωk(G) and prove various sharp inequalities concerning these parameters, which we will use to obtain refinements of the Caro-Wei Theorem, the Turán Theorem and the Hansen-Zheng Theorem among other things.