An Upper Bound on the Chromatic Number of a Graph

机译：图的色数的上界

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

A proof is provided for a graph-theoretic conjecture of Erdos and Hajnal, as follows. Let G be a graph and let k be a nonnegative integer. Suppose that for each set S included in V(G) there is a set T included in S such that T is independent in G and the cardinality of T is greater than or equal to one half the cardinality of S minus k. Then G may be vertex colored in k plus 2 colors. (Author)

著录项

作者
Folkman, J. H.;
展开▼
作者单位

展开▼
年度 1969
页码 p.1-35
总页数 35
原文格式 PDF
正文语种 eng
中图分类
关键词
Graphics ; Combinatorial analysis ; Set theory ; Colors ; Theorems;

机译：图形;组合分析;集合论;颜色;定理;

相似文献

外文文献
中文文献
专利

1. New Upper Bounds for the Independence Numbers of Graphs with Vertices in {-1,0,1}~n and Their Applications to Problems of the Chromatic Numbers of Distance Graphs [J] . E. I. Ponomarenko, A. M. Raigorodskii Mathematical notes . 2014,第1a2期

机译：{-1,0,1}〜n中具有顶点的图的独立数的新上界及其在距离图的色数问题中的应用
2. An improved upper bound for the acyclic chromatic number of 1-planar graphs [J] . Yang Wanshun, Wang Weifan, Wang Yiqiao Discrete Applied Mathematics . 2020,第1期

机译：用于1平面图的无循环色数的改进的上限
3. Improved upper bound for acyclic chromatic number of graphs [J] . Cai Jiansheng, Wang Jihui, Yu Jiguo Ars Combinatoria: An Australian-Canadian Journal of Combinatorics . 2019,第期

机译：改进的非环形彩色图形上限
4. Upper Bounds for the Total Chromatic Number of Join Graphs and Cobipartite Graphs [C] . Leandro M. Zatesko, Renato Carmo, Andre L. P. Guedes International Conference on Operations Research and Enterprise Systems . 2018

机译：用于总色彩数的上限和COBIPARTITE图表
5. On the attainability of upper bounds for the circular chromatic number of K4-minor-free graphs. [D] . Holt, Tracy. 2008

机译：关于K4次无图的圆色数的上限的可实现性。
6. Maximum common subgraph: some upper bound and lower bound results [O] . Xiuzhen Huang, Jing Lai, Steven F Jennings 2006

机译：最大公共子图：一些上限和下限结果
7. Upper bound for radio -chromatic number of graphs in connection with partition of vertex set [O] . Laxman Saha 2020

机译：用于无线电 - 与顶点集的分区相关的无线电数字的上限

An Upper Bound on the Chromatic Number of a Graph

摘要

著录项

相似文献

相关主题

期刊订阅