Back to Search Start Over

Triangle-free subgraphs with large fractional chromatic number.

Authors :
Mohar, Bojan
Wu, Hehui
Source :
Combinatorics, Probability & Computing; Jan2022, Vol. 31 Issue 1, p136-143, 8p
Publication Year :
2022

Abstract

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, Erdös 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, Rödl proved the case when $g=4$ , for arbitrary k. We prove the fractional chromatic number version of Rödl's result. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
09635483
Volume :
31
Issue :
1
Database :
Complementary Index
Journal :
Combinatorics, Probability & Computing
Publication Type :
Academic Journal
Accession number :
158785646
Full Text :
https://doi.org/10.1017/S0963548321000250