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. M. Raigorodskii

Geodesic

Parcourir par

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. M. Raigorodskii

Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 138-147

Voir la notice de l'article provenant de la source Math-Net.Ru

Résumé

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.

@article{MZM_2014_96_1_a11,
     author = {E. I. Ponomarenko and A. M. Raigorodskii},
     title = {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}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {138--147},
     publisher = {mathdoc},
     volume = {96},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/}
}

TY  - JOUR
AU  - E. I. Ponomarenko
AU  - A. M. Raigorodskii
TI  - 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
JO  - Matematičeskie zametki
PY  - 2014
SP  - 138
EP  - 147
VL  - 96
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/
LA  - ru
ID  - MZM_2014_96_1_a11
ER  -

%0 Journal Article
%A E. I. Ponomarenko
%A A. M. Raigorodskii
%T 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
%J Matematičeskie zametki
%D 2014
%P 138-147
%V 96
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/
%G ru
%F MZM_2014_96_1_a11

E. I. Ponomarenko; A. M. Raigorodskii. 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. Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 138-147. http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/