A Johnson-type graph<InlineEquation ID="IEq1"> <EquationSource Format="TEX">$J_{\pm }(n,k,t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>J</mi> <mo>±</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is a graph whose vertex set consists of the vectors in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\{-1,0,1\}^n$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">{</mo> <mo>-</mo> <mn>1</mn> <mo>,</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation> of length <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\sqrt{k}$</EquationSource> <EquationSource Format="MATHML"><math> <msqrt> <mi>k</mi> </msqrt> </math></EquationSource> </InlineEquation> and edges connect vertices with scalar product t. It is proved that the growth order of the chromatic number of both <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$J_\pm (n,2,-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>J</mi> <mo>±</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$J_\pm (n,3,-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>J</mi> <mo>±</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is logarithmic in n, and that of the graph <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$J_\pm (n,3,-2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>J</mi> <mo>±</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mo>-</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is double logarithmic in n. Bibliography: 4 titles.

ON CHROMATIC NUMBERS OF JOHNSON TYPE GRAPHS

期刊论文
发表日期：

2026年3月9日

查看全文

D. Cherkashin

摘要

A Johnson-type graph $J_{\pm }(n,k,t)$ $J_{\pm} (n, k, t)$ is a graph whose vertex set consists of the vectors in $\{-1,0,1\}^n$ ${- 1, 0, 1}^{n}$ of length $\sqrt{k}$ $\sqrt{k}$ and edges connect vertices with scalar product t. It is proved that the growth order of the chromatic number of both $J_\pm (n,2,-1)$ $J_{\pm} (n, 2, - 1)$ and $J_\pm (n,3,-1)$ $J_{\pm} (n, 3, - 1)$ is logarithmic in n, and that of the graph $J_\pm (n,3,-2)$ $J_{\pm} (n, 3, - 2)$ is double logarithmic in n. Bibliography: 4 titles.