Monochromatic Cycles in 2-Coloured Graphs
Monochromatic Cycles in 2-Coloured Graphs
复制标题
二色图中的单色循环
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. White
中科院分区：
文献类型：
--
作者：
F. Benevides;T. Luczak;A. Scott;J. Skokan;M. White
Li、Nikiforov 和 Schhelp [13] 推测任何阶数为 n 且最小度 δ(G) > 3n/4 的 2 边彩色图 G 都包含长度为 ℓ 的单色环，对于所有 ℓ ∈ [4, ⌈n/2⌉]。我们在足够大的 n 下证明了这个猜想，并且还找到了不包含所有此类环的所有 δ(G)=3n/4 的 2 边彩色图。最后，我们证明，对于所有 δ>0 和 n>n0(δ)，如果 G 是 n 阶 2 边彩色图，且 δ(G) ≥ 3n/4，则一个颜色类要么包含长度至少为 (2/3+δ/2)n 的单色循环，要么包含所有长度 ℓ ε [3, (2/3−δ)n] 的单色循环。
Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ(G) > 3n/4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈n/2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ(G)=3n/4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n>n0(δ), if G is a 2-edge coloured graph of order n with δ(G) ≥ 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2)n, or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ)n].