δ_k-small sets in graphs

2012/11/15 by Asen Bojilov, Bojilov, Asen, Nedyalko Nenov +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1211.3689

arxiv created 2012/11/15 · openalex publication_date 2012/11/15 · arxiv updated 2012/11/16 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28

Abstract

Let G be a simple n-vertex graph and W⊆\V(G). We say that W is a δ_k-small set if √[k]\frac∑_{v∈ W}d^k(v)\abs W≤ n-\abs W. Let φ^(k)(G) denote the smallest natural number r such that \V(G) decomposes into r δ_k-small sets, and let α^(k)(G) denote the maximal number of vertices in a δ_k-small set of G. In this paper we obtain bounds for α^(k)(G) and φ^(k)(G). Since φ^(k)(G)≤ω(G)≤χ(G) and α(G)≤α^(k)(G), we obtain also bounds for the clique number ω(G), the chromatic number χ(G) and the independence number α(G).

Citations

• An Inequality for Generalized Chromatic Graphs

Cited by

• New measures of graph irregularity

Related

• Partitions of graphs into small and large sets
• On the chromatic numbers of small-dimensional Euclidean spaces
• Conjectured lower bound for the clique number of a graph
• Clique minors in graphs with a forbidden subgraph
• Number of sets with small sumset and the clique number of random Cayley graphs