RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mat. Sb., 2013, Volume 204, Number 4, Pages 49–78 (Mi msb7830)  

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.

Funding Agency Grant Number
Russian Foundation for Basic Research 12-01-00683
Ministry of Education and Science of the Russian Federation НШ-2519.2012.1

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/msb7830
  • https://doi.org/10.4213/sm7830
  • http://mi.mathnet.ru/eng/msb/v204/i4/p49

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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:
    1. 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  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    2. 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  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    3. S. N. Popova, “Zero-one laws for random distance graphs with vertices in $\{0,1\}^n$”, Dokl. Math., 90:2 (2014), 535–538  crossref  crossref  zmath  isi  elib  elib  scopus
    4. V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929  mathnet  crossref  crossref  mathscinet  isi  elib
    5. M. M. Pyaderkin, “On the stability of the ErdH os-Ko-Rado theorem”, Dokl. Math., 91:3 (2015), 290–293  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    6. 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  mathnet  crossref  isi  elib
    7. M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319  mathnet  crossref  crossref  mathscinet  isi  elib
    8. 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  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    9. Ph. Pushnyakov, “On the Number of Edges in Induced Subgraphs of a Special Distance Graph”, Math. Notes, 99:4 (2016), 545–551  mathnet  crossref  crossref  mathscinet  isi  elib
    10. S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  mathnet  crossref  crossref  mathscinet  elib
    11. A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528  mathnet  crossref  crossref  mathscinet  isi  elib
    12. A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546  mathnet  crossref  crossref  mathscinet  isi  elib
    13. A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117  mathnet  crossref  crossref  mathscinet  isi  elib
    14. 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  mathnet  crossref  isi  elib
    15. 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  mathnet  crossref  crossref  isi  elib
    16. F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298  mathnet  crossref
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:476
    Full text:125
    References:59
    First page:64

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020