Document Type
Lecture
Publication Date
9-3-2014
Abstract
A classic theorem states that for any k and l, there exists a graph with girth at least l, and chromatic number at least k. In 1970’s, Erd˝os and Hajnal proposed a conjecture that for any k, l, there exists a number f(k,l), such that if G has chromatic number at least f(k,l), then it contains a subgraph with chromatic number at least k and girth at least l. In 1977, Rödl proved that it is true for l = 3, that is, if the chromatic number is sufficiently large enough, that it contains a triangle-free subgraph with large chromatic number. Recently, we proved an analogous result for fractional chromatic number: for any k, there exists a f(k), such that if the fractional chromatic number is at least f(k), then it contains a triangle-free subgraph with fractional chromatic number at least k. This is joint work with Professor Bojan Mohar at Simon Fraser University.
Relational Format
presentation
Recommended Citation
Wu, Hehui, "Triangle-free subgraph with high fractional chromatic number" (2014). Combinatorics Seminar. 52.
https://egrove.olemiss.edu/math_combinatorics/52
