Erdős-Hajnal for cap-free graphs
Erdős-Hajnal for cap-free graphs
复制标题
ErdÅs-Hajnal 用于无上限图
DOI：
10.1016/j.jctb.2021.07.006
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Seymour, Paul
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Seymour, Paul
图G中的一个“帽”是G的一个导出子图，它由一个至少有四个长度的圈和一个另外一个顶点组成，这个圈中恰好有两个相邻的顶点，而“房子”是最小的，在五个顶点上。目前尚不清楚是否存在ε>；0使得每个不含房子的图G至少有一个团或稳定的基数集|G|ε；这是ErdőS-哈杰纳尔猜想的最小公开情形，一直是许多研究的主题。我们证明了存在ε>；0使得每个无顶图G至少有一个团或稳定的基数集|G|ε。
A “cap” in a graph G is an induced subgraph of G that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in the cycle, adjacent to each other, and the “house” is the smallest, on five vertices. It is not known whether there exists ε> 0 such that every graph G containing no house has a clique or stable set of cardinality at least| G| ε; this is the smallest open case of the Erdős-Hajnal conjecture and has been the subject of much study. We prove that there exists ε> 0 such that every graph G with no cap has a clique or stable set of cardinality at least| G| ε.
登录
查看更多内容
识别 Meyniel 图的多项式算法
DOI：
--
发表时间：
1984
期刊：
影响因子：
--
作者：
M. Burlet;J. Fonlupt
通讯作者：
J. Fonlupt
影响因子：
0.8
作者：
V. Rödl
通讯作者：
V. Rödl
路径和反路径的 Erdős-Hajnal 猜想
DOI：
--
发表时间：
2013
期刊：
Journal of combinatorial theory. Series B (Print)
影响因子：
--
作者：
N. Bousquet;Aurélie Lagoutte;Stéphan Thomassé
通讯作者：
Stéphan Thomassé
关于图的跨越子图
DOI：
--
发表时间：
1977
期刊：
影响因子：
--
作者：
A. Hajnal
通讯作者：
A. Hajnal
排除路径和反路径
DOI：
--
发表时间：
2015
期刊：
Comb.
影响因子：
--
作者：
M. Chudnovsky;P. Seymour
通讯作者：
P. Seymour