The Minimum Degree Removal Lemma Thresholds
EUROCOMB’23
485–490
Allen, P., Böttcher, J., Griffiths, S., Kohayakawa, Y., & Morris, R. (2013). The chromatic thresholds of graphs. Advances in Mathematics, 235, 261-295.
https://doi.org/10.1016/j.aim.2012.11.016
Alon, N. (2002). Testing subgraphs in large graphs. Random Structures & Algorithms, 21(3-4), 359-370.
https://doi.org/10.1002/rsa.10056
Alon, N., & Spencer, J. (2016). The probabilistic method. John Wiley & Sons.
Andrásfai, B., Erdős, P., & Sos, V. (1974). On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Mathematics, 8(3), 205-218.
https://doi.org/10.1016/0012-365X(74)90133-2
Brandt, S. (1999). On the structure of dense triangle-free graphs. Combinatorics, Probability and Computing, 8(3), 237-245.
https://doi.org/10.1017/S0963548399003831
Brandt, S., & Thomassé, S. (2011). Dense triangle-free graphs are four-colorable: A solution to the Erdős-Simonovits problem. preprint.
Chen, C.C., Jin, G., & Koh, K. (1997). Triangle-free graphs with large degree. Combinatorics, Probability and Computing, 6(4), 381-396.
https://doi.org/10.1017/S0963548397003167
Ebsen, O., & Schacht, M. (2020). Homomorphism thresholds for odd cycles. Combinatorica, 40(1), 39-62.
https://doi.org/10.1007/s00493-019-3920-8
Erdős, P. (1964). On extremal problems of graphs and generalized graphs. Israel Journal of Mathematics, 2(3), 183-190.
https://doi.org/10.1007/BF02759942
Erdős, P., & Simonovits, M. (1973). On a valence problem in extremal graph theory. Discrete Mathematics, 5(4), 323-334.
https://doi.org/10.1016/0012-365X(73)90126-X
Fox, J. (2011). A new proof of the graph removal lemma. Annals of Mathematics, 561-579.
https://doi.org/10.4007/annals.2011.174.1.17
Fox, J., & Wigderson, Y. (2021). Minimum degree and the graph removal lemma. Journal of Graph Theory.
https://doi.org/10.1002/jgt.22891
Goddard, W., & Lyle, J. (2011). Dense graphs with small clique number. Journal of Graph Theory, 66(4), 319-331.
https://doi.org/10.1002/jgt.20505
Häggkvist, R. (1982). Odd cycles of specified length in non-bipartite graphs. In North-
https://doi.org/10.1016/S0304-0208(08)73552-7
Holland Mathematics Studies, volume 62, 89-99. Elsevier.
Jin, G. (1995). Triangle-free four-chromatic graphs. Discrete Mathematics, 145(1-3), 151-170.
https://doi.org/10.1016/0012-365X(94)00063-O
Letzter, S., & Snyder, R. (2019). The homomorphism threshold of {C3,C5}-free graphs. Journal of Graph Theory, 90(1), 83-106.
https://doi.org/10.1002/jgt.22369
Luczak, T. (2006). On the structure of triangle-free graphs of large minimum degree. Combinatorica, 26(4), 489-493.
https://doi.org/10.1007/s00493-006-0028-8
Luczak, T., & Thomassé, S. (2010). Coloring dense graphs via VC-dimension. arXiv preprint arXiv:1007.1670.
Lyle, J. (2011). On the chromatic number of H-free graphs of large minimum degree. Graphs and Combinatorics, 27(5), 741-754.
https://doi.org/10.1007/s00373-010-0994-x
Nakar, Y., & Ron, D. (2018). On the testability of graph partition properties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018).
Oberkampf, H., & Schacht, M. (2020). On the structure of Dense graphs with bounded clique number. Combinatorics, Probability and Computing, 29(5), 641-649.
https://doi.org/10.1017/S0963548319000324
Ruzsa, I. Z., & Szemerédi, E. (1978). Triple systems with no six points carrying three triangles. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai,, volume 18, pages 939-945. North-Holland, Amsterdam-New York.
Sankar, M. (2022). Homotopy and the Homomorphism Threshold of Odd Cycles. arXiv preprint arXiv:2206.07525.
Thomassen, C. (2002). On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica, 22(4), 591-596.
https://doi.org/10.1007/s00493-002-0009-5
Thomassen, C. (2007). On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica, 27(2), 241-243.
https://doi.org/10.1007/s00493-007-0054-1
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Lior Gishboliner, Benny Sudakov, Zhihan Jin