Abstract:
It is established that there exist sequences of distance graphs Gn⊂Rn, with chromatic numbers which grow exponentially, but, at the same time, without cliques or cycles of a given size.
Bibliography: 42 titles.
Keywords:
distance graph, random graph, chromatic number, clique, cycle.
Citation:
E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508–538
\Bibitem{DemRaiRub13}
\by E.~E.~Demekhin, A.~M.~Raigorodskii, O.~I.~Rubanov
\paper Distance graphs having large chromatic numbers and containing no cliques or cycles of a~given size
\jour Sb. Math.
\yr 2013
\vol 204
\issue 4
\pages 508--538
\mathnet{http://mi.mathnet.ru/eng/sm7830}
\crossref{https://doi.org/10.1070/SM2013v204n04ABEH004310}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3097579}
\zmath{https://zbmath.org/?q=an:1268.05070}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2013SbMat.204..508D}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000320302700003}
\elib{https://elibrary.ru/item.asp?id=19066661}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84888343984}
Linking options:
https://www.mathnet.ru/eng/sm7830
https://doi.org/10.1070/SM2013v204n04ABEH004310
https://www.mathnet.ru/eng/sm/v204/i4/p49
This publication is cited in the following 21 articles:
Yu. A. Demidovich, M. E. Zhukovskii, “Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces”, Math. Notes, 109:5 (2021), 727–734
Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
Yu. A. Demidovich, “Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space”, Math. Notes, 106:1 (2019), 38–51
A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395
Sagdeev A.A. Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033
A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117
A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83
A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528
A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546
A.A. Sagdeev, “On a Frankl–Rödl theorem and its geometric corollaries”, Electronic Notes in Discrete Mathematics, 61 (2017), 1033
M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319
S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in Zn”, Sb. Math., 207:3 (2016), 458–478
Ph. Pushnyakov, “On the Number of Edges in Induced Subgraphs of a Special Distance Graph”, Math. Notes, 99:4 (2016), 545–551
S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75
L. Iskhakov, M. Mironov, “Diameters of random distance graphs”, Journal of Mathematical Sciences, 227:4 (2017), 407–418
V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929
M. M. Pyaderkin, “On the stability of the ErdH os-Ko-Rado theorem”, Dokl. Math., 91:3 (2015), 290–293
Ph. A. Pushnyakov, “A new estimate for the number of edges in induced subgraphs of a special distance graph”, Problems Inform. Transmission, 51:4 (2015), 371–377
A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. Math., 78:1 (2014), 59–89
S. N. Popova, “Zero-one laws for random distance graphs with vertices in {0,1}n”, Dokl. Math., 90:2 (2014), 535–538
Citation in format AMSBIB
Contact us: