论文标题
带宽较小的带宽的三色拉姆西数量与二分图
Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
论文作者
论文摘要
图$ \ MATHCAL {H} =（W，e_ \ Mathcal {h}）$被认为具有{\ em bandwidth}，如果存在$ w $的标签为$ w_1，w_1，w_2，w_2，\ dots，w_2，w_n $，w_n $ w_n $ w_n $ E_ \ Mathcal {H} $。我们说$ \ nathcal {h} $是{\ em平衡$（β，δ）$ - graph}，如果它是带宽最多的二分组图，最多最多$β| $，并且最多最高$δ$，并且它也具有适当的2颜色$χχχχχχ[2] $ [2] $ $ ||χ^{ - 1}（1）| - |χ^{ - 1}（2）|| \leqβ|χ^{ - 1}（2）| $。 在本文中，我们证明每$γ> 0 $和每个自然数量$δ$，都存在一个常数$β> 0 $，以使每个均衡的$（β，δ）$ - graph $ - graph $ \ nathcal {h} $ on $ n $ dertices on $ n $ dertices上的$ n $ dertices上，我们有$ r（\ nathcal {h}，\ nathcal {h}，\ mathcalcal for，所有足够大的奇数$ n $。对于几类图形，上限是锋利的。令$θ_{n，t} $是由$ t $内部不相交的$ n $组成的图形，所有共享相同端点。作为推论，对于每个固定的$ t \ geq 1 $，$ r（θ_{n，t}，θ_{n，t}，c_ {nt+λ}）=（3t+o（3t+o（1））n，$λ= 0 $ nt $ nt $，$ nt $是奇数，并且$λ= 1 $ nt $ nt $均为$ nt $。特别是，我们有$ r（c_ {2n}，c_ {2n}，c_ {2n+1}）=（6+o（1））n $，这是Figaj和oluczak（2018）结果的特殊情况。
A graph $\mathcal{H}=(W,E_\mathcal{H})$ is said to have {\em bandwidth} at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots,w_n$ such that $|i-j|\leq b$ for every edge $w_iw_j\in E_\mathcal{H}$. We say that $\mathcal{H}$ is a {\em balanced $(β,Δ)$-graph} if it is a bipartite graph with bandwidth at most $β|W|$ and maximum degree at most $Δ$, and it also has a proper 2-coloring $χ:W\rightarrow[2]$ such that $||χ^{-1}(1)|-|χ^{-1}(2)||\leqβ|χ^{-1}(2)|$. In this paper, we prove that for every $γ>0$ and every natural number $Δ$, there exists a constant $β>0$ such that for every balanced $(β,Δ)$-graph $\mathcal{H}$ on $n$ vertices we have $$R(\mathcal{H}, \mathcal{H}, C_n) \leq (3+γ)n$$ for all sufficiently large odd $n$. The upper bound is sharp for several classes of graphs. Let $θ_{n,t}$ be the graph consisting of $t$ internally disjoint paths of length $n$ all sharing the same endpoints. As a corollary, for each fixed $t\geq 1$, $R(θ_{n, t},θ_{n, t}, C_{nt+λ})=(3t+o(1))n,$ where $λ=0$ if $nt$ is odd and $λ=1$ if $nt$ is even. In particular, we have $R(C_{2n},C_{2n}, C_{2n+1})=(6+o(1))n$, which is a special case of a result of Figaj and Łuczak (2018).
