No CrossRef data available.
Article contents
Triangle-free subgraphs with large fractional chromatic number
Part of:
Graph theory
Published online by Cambridge University Press: 29 June 2021
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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.
MSC classification
Information
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2021. Published by Cambridge University Press
Footnotes
†
Supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada Research Chairs program, and by the Research Project J1-8130 of ARRS (Slovenia).
‡
Part of this work was done while the author was a PIMS Postdoctoral Fellow at the Department of Mathematics, Simon Fraser University, Burnaby, B.C.
References
Ajtai, M., Komlós, J. and Szemerédi, E. (1980) A note on Ramsey numbers. J. Comb. Theory Ser. A 29 354–360.Google Scholar
Bollobás, B. and Sauer, N. (1976) Uniquely colourable graphs with large girth. Canad. J. Math. 28 1340–1344.CrossRefGoogle Scholar
Bukh, B. Interesting problems. http://www.borisbukh.org/problems.html. See also http://www.openproblemgarden. org/category/bukh_boris.Google Scholar
Dellamonica, D., Koubek, V., Martin, D. M. and Rödl, V. (2011) On a conjecture of Thomassen concerning subgraphs of large girth. J. Graph Theory 67 316–331.CrossRefGoogle Scholar
Dellamonica, D. and Rödl, V. (2011) A note on Thomassen’s conjecture. J. Comb. Theory Ser. B 101 509–515.Google Scholar
Erdös, P. (1969) Problems and results in combinatorial analysis and graph theory. In Proof Techniques in Graph Theory (Harary, F., ed.), Academic Press, New York, pp. 27–35.Google Scholar
Godsil, C. and Royle, G. (2001) Algebraic Graph Theory. Springer-Verlag, New York.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2004) Every graph of sufficiently large average degree contains a
$C_4$
-free subgraph of large average degree. Combinatorica 24 155–162.CrossRefGoogle Scholar
$C_4$
-free subgraph of large average degree. Combinatorica 24 155–162.CrossRefGoogle ScholarKim, J. H. (1995) The Ramsey number R(3,t) has order of magnitude
$t^2/\log t$
. Random Struct. Algorithms 7 173–207.Google Scholar
$t^2/\log t$
. Random Struct. Algorithms 7 173–207.Google ScholarLovász, L. (1978) Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory Ser. A 25 319–324.CrossRefGoogle Scholar
Mohar, B. and Wu, H. (2016) Dichromatic number and fractional chromatic number. Forum Math. Sigma 4 e32, 14 p. https://doi.org/10.1017/fms.2016.28.CrossRefGoogle Scholar
Mohar, B. and Wu, H. (2020) Fractional chromatic number of a random subgraph. J. Graph Theory 95 467–472. https://doi.org/10.1002/jgt.22571.CrossRefGoogle Scholar
Pyber, L., Rödl, V. and Szemerédi, E. (1995) Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63 41–54.CrossRefGoogle Scholar
Rödl, V. (1977) On the chromatic number of subgraphs of a given graph. Proc. Am. Math. Soc. 64 370–371.Google Scholar
Zhu, X. (1996) Uniquely H-colorable graphs with large girth. J. Graph Theory 23 33–41.3.0.CO;2-L>CrossRefGoogle Scholar
You have
Access