• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Coloring tournaments: From local to global
【24h】

Coloring tournaments: From local to global

机译：着色锦标赛：从当地到全球

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

摘要

The chromatic number of a directed graph D is the minimum number of colors needed to color the vertices of D such that each color class of D induces an acyclic subdigraph. Thus, the chromatic number of a tournament T is the minimum number of transitive subtournaments which cover the vertex set of T. We show in this note that tournaments are significantly simpler than graphs with respect to coloring. Indeed, while undirected graphs can be altogether "locally simple" (every neighborhood is a stable set) and have large chromatic number, we show that locally simple tournaments are indeed simple. In particular, there is a function f such that if the out-neighborhood of every vertex in a tournament T has chromatic number at most c, then T has chromatic number at most f(c). This answers a question of Berger et al. (C) 2019 Elsevier Inc. All rights reserved.
机译：定向图D的彩色数量是彩色D的顶点所需的最小颜色，使得D的每种颜色等级引起无循环子层。 因此，锦标赛T的彩色数量是覆盖T的顶点组的最小值的传递亚类。我们在本说明中，锦标赛比着色的图表显着更简单。 实际上，虽然无向图形可以完全“本地简单”（每个社区是稳定的集合）并且具有大的彩色数量，但我们表明本地简单的锦标赛确实很简单。 具体地，存在一个函数f，使得如果锦标赛T中每个顶点的外邻域在大多数c上具有彩色数字，则t在大多数f（c）上具有色度。 这回答了Berger等人的问题。 （c）2019 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号