Back to Search
Start Over
Triangle-free subgraphs with large fractional chromatic number.
- 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]
- Subjects :
- SUBGRAPHS
CHARTS, diagrams, etc.
CHROMATIC polynomial
INTEGERS
LOGICAL prediction
Subjects
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