Triangle-free subgraphs with large fractional chromatic number. (29th January 2022)

• Record Type: Journal Article
• Authors: Mohar, Bojan; Wu, Hehui
• Is Part Of: Combinatorics, probability and computing. Volume 31:Number 1(2022)
• Page Start: 136
• Page End: 143
• Publication Date: 2022-01-29
• Subjects: chromatic number -- fractional chromatic number -- Erdös–Hajnal conjecture; 05C15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000250
• Languages: English
• ISSNs: 0963-5483

Abstract

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.