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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find




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

Izvestiya: Mathematics, 2014, Volume 78, Issue 1, Pages 59–89
DOI: https://doi.org/10.1070/IM2014v078n01ABEH002680 (Mi im7962) 		 
This article is cited in 12 scientific papers (total in 12 papers)

Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers

A. B. Kupavskii

Moscow Institute of Physics and Technology
English version PDF (446 kB) Citations (12)
References:
PDF
HTML
DOI: https://doi.org/10.1070/IM2014v078n01ABEH002680
Abstract: We study distance graphs with exponentially large chromatic numbers and without $k$-cliques, that is, complete subgraphs of size $k$. Explicit constructions of such graphs use vectors in the integer lattice. For a large class of graphs we find a sharp threshold for containing a $k$-clique. This enables us to improve the lower bounds for the maximum of the chromatic numbers of such graphs. We give a new probabilistic approach to the construction of distance graphs without $k$-cliques, and this yields better lower bounds for the maximum of the chromatic numbers for large $k$.
Keywords: distance graph, chromatic number, clique number, Nelson problem.
Received: 08.02.2012
Revised: 12.07.2012
Russian version:
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 2014, Volume 78, Issue 1, Pages 65–98
DOI: https://doi.org/10.4213/im7962
Bibliographic databases:
Document Type: Article
UDC: 519.174.7+519.176+519.175.4
MSC: 52C10, 05C10, 05C15, 05C69, 05D10, 05C50
Language: English
Original paper language: Russian
Citation: A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. RAN. Ser. Mat., 78:1 (2014), 65–98; Izv. Math., 78:1 (2014), 59–89
Citation in format AMSBIB
\Bibitem{Kup14}
\by A.~B.~Kupavskii
\paper Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
\jour Izv. RAN. Ser. Mat.
\yr 2014
\vol 78
\issue 1
\pages 65--98
\mathnet{http://mi.mathnet.ru/im7962}
\crossref{https://doi.org/10.4213/im7962}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3204659}
\zmath{https://zbmath.org/?q=an:1287.05029}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2014IzMat..78...59K}
\elib{https://elibrary.ru/item.asp?id=21276260}
\transl
\jour Izv. Math.
\yr 2014
\vol 78
\issue 1
\pages 59--89
\crossref{https://doi.org/10.1070/IM2014v078n01ABEH002680}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000332236500004}
\elib{https://elibrary.ru/item.asp?id=21866787}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84894711516}
Linking options:
  • https://www.mathnet.ru/eng/im7962
  • https://doi.org/10.1070/IM2014v078n01ABEH002680
  • https://www.mathnet.ru/eng/im/v78/i1/p65
    • This publication is cited in the following 12 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Statistics & downloads:
    Abstract page:506
    Russian version PDF:192
    English version PDF:14
    References:61
    First page:30
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024