Triangle-free subgraphs with large fractional chromatic number

被引：0

作者：

Mohar, Bojan ^{[1
]}

Wu, Hehui ^{[2
]}

机构：

[1] Simon Fraser Univ, Dept Math, Burnaby, BC, Canada

[2] Fudan Univ, Shanghai Ctr Math Sci, Shanghai, Peoples R China

来源：

COMBINATORICS PROBABILITY AND COMPUTING | 2022年 / 31卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

chromatic number; fractional chromatic number; Erdos-Hajnal conjecture; COLORABLE GRAPHS;

D O I：

10.1017/S0963548321000250

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is well known that for any integers k and g, there is a graph with chromatic number at least k and girth at least g. In 1960s, Erdos and Hajnal conjectured that for any k and g, there exists a number h(k,g), such that every graph with chromatic number at least h(k,g) contains a subgraph with chromatic number at least k and girth at least g. In 1977, Rodl proved the case when $g=4$ , for arbitrary k. We prove the fractional chromatic number version of Rodl's result.

引用

页码：136 / 143

页数：8

共 18 条

[1] A NOTE ON RAMSEY NUMBERS [J].