|
This article is cited in 16 scientific papers (total in 16 papers)
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
E. E. Demekhina, A. M. Raigorodskiiab†, O. I. Rubanovab
a M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Moscow Institute of Physics and Technology (State University)
Abstract:
It is established that there exist sequences of distance graphs $G_n\subset\mathbb R^n$, 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.
† Author to whom correspondence should be addressed
DOI:
https://doi.org/10.4213/sm7830
 Full text:
PDF file (732 kB)
References:
PDF file
HTML file
English version:
Sbornik: Mathematics, 2013, 204:4, 508–538
Bibliographic databases:
     
UDC:
519.112.4+519.174+519.176
MSC: 05C15, 05C35, 05D10
Received: 14.12.2010 and 09.12.2011
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”, Mat. Sb., 204:4 (2013), 49–78; Sb. Math., 204:4 (2013), 508–538
Citation in format AMSBIB
\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 Mat. Sb.
\yr 2013
\vol 204
\issue 4
\pages 49--78
\mathnet{http://mi.mathnet.ru/msb7830}
\crossref{https://doi.org/10.4213/sm7830}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3097579}
\zmath{https://zbmath.org/?q=an:1268.05070}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2013SbMat.204..508D}
\elib{http://elibrary.ru/item.asp?id=19066661}
\transl
\jour Sb. Math.
\yr 2013
\vol 204
\issue 4
\pages 508--538
\crossref{https://doi.org/10.1070/SM2013v204n04ABEH004310}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000320302700003}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84888343984}
Linking options:
http://mi.mathnet.ru/eng/msb7830https://doi.org/10.4213/sm7830 http://mi.mathnet.ru/eng/msb/v204/i4/p49
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:
-
A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479
 -
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
-
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
-
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 $\mathbb Z^n$”, 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
-
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. 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
-
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
-
F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh
nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298
|
| Number of views: |
| This page: | 476 | | Full text: | 125 | | References: | 59 | | First page: | 64 |
|
Terms of Use