- PII
- S3034504925020073-1
- DOI
- 10.7868/S3034504925020073
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 522 / Issue number 1
- Pages
- 40-49
- Abstract
- The paper describes a new method for constructing triangle-free graphs with an arbitrarily large chromatic number. The method is substantiated using properties of various types of ultrafilter extensions of functions and predicates.
- Keywords
- граф граф без треугольников хроматическое число ультрафильтр ультрарасширение
- Date of publication
- 01.04.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 58
References
- 1. P. Erdo s, Graph Theory and Probability. Canadian Journal of Mathematics, 11, 34–38 (1959).
- 2. А.А. Зыков, О некоторых свойствах линейных комплексов. Математический сборник, 24 (66), 163–188 (1949).
- 3. J. Mycielski, Sur le coloriage des graphs. Colloquium Mathematicum 3, 161–162 (1955).
- 4. M. Shtibitz, Beitrage zur Theorie der farbungskritschen Graphen. Technische Universitat Ilmenau, Habilitation Thesis (1985).
- 5. L. Lova´sz, Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25 (3), 319–324 (1978).
- 6. J.E. Greene, A new short proof of Kneser’s conjecture. American Mathematical Monthly, 109 (10), 918–920 (1978).
- 7. J. Matousˇek, A combinatorial proof of Kneser’s conjecture. Combinatorica, 24 (1), 163–170 (2004).
- 8. J.P. Burling, On coloring problems of families of prototypes. Boulder: University of Colorado, PhD thesis (1965).
- 9. A. Pawlik, J. Kozik, et al, Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B, 105(5), 6–10 (2014).
- 10. L. Lova´sz, On chromatic number of finite set– systems. Acta Math. Acad. Sci. Hungar, 19, 59– 67 (1968).
- 11. P. O’Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. I. Graph description. Geombinatorics, 9 (3), 145–152 (2000).
- 12. P. O’Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. II. Graph embedding. Geombinatorics, 9 (4), 180–193 (2000).
- 13. A.M. Raigorodskii, Cliques and cycles in distance graphs and graphs of diameters. Discrete Geometry and Algebraic Combinatorics. AMS. Contemp. Math., 625, 93–109 (2014).
- 14. N. Alon, A. Kupavskii, Two notions of unit distance graphs. Journal of Combinatorial Theory, Series A, 125, 1–17 (2014).
- 15. W.W. Comfort, S. Negrepontis, The theory of ultrafilters. Springer, Berlin (1974).
- 16. N. Hindman, D. Strauss, Algebra in the Stone– Cech Compactification. 2nd ed., revised and expanded, W. de Gruyter, Berlin–N.Y. (2012).
- 17. V. Goranko, Filter and ultrafilter extensions of structures: universal-algebraic aspects. Preprint (2007).
- 18. D.I. Saveliev, Ultrafilter extensions of models. Lecture Notes in AICS, 6521, 162–177 (2011).
- 19. D.I. Saveliev, On ultrafilter extensions of models. In: S.-D. Friedman et al. (eds.). The Infinity Project Proc. CRM Documents 11, Barcelona, 599–616 (2012).
- 20. N.L. Poliakov, D.I. Saveliev, On ultrafilter extensions of first-order models and ultrafilter interpretations. Arch. Math. Logic 60, 625–681 (2021).
- 21. N.L. Polyakov, On the Canonical Ramsey Theorem of Erdos and Rado and Ramsey Ultrafilters. Dokl. Math. 108, 392–401 (2023).
- 22. B. Jo´nsson, A. Tarski, Boolean algebras with operators. Part I: Amer. J. Math. 73 (4), 891–939 (1951); Part II: ibid. 74 (1), 127–162 (1952).
- 23. N.G. de Bruijn, P. Erdo s, A colour problem for infinite graphs and a problem in the theory of relations. Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen. Series A, mathematical sciences, 54(5), 371–373 (1951).
- 24. I. Shur, U¨ ber die Kongruenz xm + ym = zm (mod p). Jahresber. Deutsche Math.-Verein. 25, 114–116 (1916).
- 25. A. Sisto, Exponential Triples. The Electronic Journal of Combinatorics, 18 (1), P147 (2011).
