E. I. Ponomarenko, A. M. Raigorodskii, “New Upper Bounds for the Independence Numbers of Graphs with Vertices in <nobr>$\{-1,0,1\}^n$</nobr> and Their Applications to Problems of the Chromatic Numbers of Distance Graphs”, Mat. Zametki, 2014, Volume 96, Issue 1,Pages <nobr>138

This article is cited in 11 papers

New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs

E. I. Ponomarenko^a, A. M. Raigorodskii^ba

^a Moscow Institute of Physics and Technology (State University)
^b M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Upper bounds for the independence numbers in the graphs with vertices at $\{-1, 0,1\}^n$ are improved. Their applications to problems of the chromatic numbers of distance graphs are studied.

Keywords: graph, hypergraph, independence number, chromatic number, distance graph, Hamming distance, Nelson–Erdős–Hadwiger problem.

UDC: 519.17

Received: 08.08.2013
Revised: 26.11.2013

DOI: 10.4213/mzm10352