RUS
ENG
Full version
JOURNALS
// Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia
// Archive
Dokl. RAN. Math. Inf. Proc. Upr.,
2025
Volume 522,
Pages
40–49
(Mi danma633)
MATHEMATICS
On a ñombinatorial application of ultrafilter theory: a new construction of triangle-free graphs with arbitrarily large chromatic number
N. L. Poliakov
National Research University Higher School of Economics, Moscow
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:
graph, triangle-free graph, chromatic number, ultrafilter, ultrafilter extension.
UDC:
519.15,
519.17
Presented:
A. L. Semenov
Received: 13.11.2024
Revised: 26.12.2024
Accepted: 20.03.2025
DOI:
10.31857/S2686954325020073
English version:
Doklady Mathematics, 2025,
111
:2,
126–133
Bibliographic databases:
©
Steklov Math. Inst. of RAS
, 2026
