...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Partitions of graphs into small and large sets
【24h】

Partitions of graphs into small and large sets

机译：将图分为大和小集

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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, deg(v)≤n-|A|+k. A subset B ∪ V(G) is called k-large if, for every vertex u ε B, deg(u)≥|B|-k-1. Moreover, we denote by φ_k(G) the minimum integer t such that there is a partition of V(G) into tk-small sets, and by Ω_k(G) the minimum integer t such that there is a partition of V(G) into tk-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, Turán's Theorem and the Hansen-Zheng Theorem among other things.
机译：令G为n个顶点上的图。如果对于每个顶点vεA，deg（v）≤n-| A | + k，我们称顶点集V（G）k小的子集A。如果对于每个顶点uεB，deg（u）≥| B | -k-1，则子集B∪V（G）称为k大。此外，我们用φ_k（G）表示最小整数t，从而将V（G）划分为tk个小集合;用Ω_k（G）表示最小整数t，从而存在V（G）的划分。 ）放入tk大集。在本文中，我们将显示k个小集（分别为k个大集）与图的k个独立数，集团数和色数之间的紧密联系。我们将开发贪婪算法以在线性时间内计算φ_k（G）和Ω_k（G）并证明与这些参数有关的各种尖锐不等式，我们将使用它们来获得Caro-Wei定理，Turán定理和Hansen-Zheng的精化定理除其他外。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号