Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces

Yu A. Demidovich; M. E. Zhukovskii

doi:10.1134/S0001434621050060

Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces

Yu A. Demidovich^*, M. E. Zhukovskii

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Abstract: We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.

Original language	English (US)
Pages (from-to)	727-734
Number of pages	8
Journal	Mathematical Notes
Volume	109
Issue number	5-6
DOIs	https://doi.org/10.1134/S0001434621050060
State	Published - May 2021

Bibliographical note

Funding Information:
The proof of Theorem was supported by the Russian Foundation for Basic Research (science grant no. 18-01-00355) and by the program “Leading Scientific Schools” (grant no. NSh-2540.2020.1). The proof of Corollary was supported by the Grant of the Government of the Russian Federation for the state support of scientific research supervised by leading scientists (agreement no. 075-15-2019-1926).

Publisher Copyright:
© 2021, Pleiades Publishing, Ltd.

Keywords

chromatic number
distance graph
graph girth
linear-algebraic method

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1134/S0001434621050060

Cite this

@article{520a87ab21f74772be454cb9c688ffe7,

title = "Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces",

abstract = "Abstract: We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.",

keywords = "chromatic number, distance graph, graph girth, linear-algebraic method",

author = "Demidovich, {Yu A.} and Zhukovskii, {M. E.}",

note = "Funding Information: The proof of Theorem was supported by the Russian Foundation for Basic Research (science grant no. 18-01-00355) and by the program “Leading Scientific Schools” (grant no. NSh-2540.2020.1). The proof of Corollary was supported by the Grant of the Government of the Russian Federation for the state support of scientific research supervised by leading scientists (agreement no. 075-15-2019-1926). Publisher Copyright: {\textcopyright} 2021, Pleiades Publishing, Ltd.",

year = "2021",

month = may,

doi = "10.1134/S0001434621050060",

language = "English (US)",

volume = "109",

pages = "727--734",

journal = "Mathematical Notes",

issn = "0001-4346",

publisher = "Springer Science + Business Media",

number = "5-6",

}

TY - JOUR

T1 - Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces

AU - Demidovich, Yu A.

AU - Zhukovskii, M. E.

N1 - Funding Information: The proof of Theorem was supported by the Russian Foundation for Basic Research (science grant no. 18-01-00355) and by the program “Leading Scientific Schools” (grant no. NSh-2540.2020.1). The proof of Corollary was supported by the Grant of the Government of the Russian Federation for the state support of scientific research supervised by leading scientists (agreement no. 075-15-2019-1926). Publisher Copyright: © 2021, Pleiades Publishing, Ltd.

PY - 2021/5

Y1 - 2021/5

N2 - Abstract: We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.

AB - Abstract: We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.

KW - chromatic number

KW - distance graph

KW - graph girth

KW - linear-algebraic method

UR - http://www.scopus.com/inward/record.url?scp=85113200818&partnerID=8YFLogxK

U2 - 10.1134/S0001434621050060

DO - 10.1134/S0001434621050060

M3 - Article

AN - SCOPUS:85113200818

SN - 0001-4346

VL - 109

SP - 727

EP - 734

JO - Mathematical Notes

JF - Mathematical Notes

IS - 5-6

ER -

Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this