Monochromatic Cycle Partitions of 2-Coloured Graphs with Minimum Degree 3n/4
Monochromatic Cycle Partitions of 2-Coloured Graphs with Minimum Degree 3n/4
复制标题
最小次数为 3n/4 的 2 色图的单色循环划分
DOI：
--
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
Shoham Letzter
中科院分区：
文献类型：
--
作者：
Shoham Letzter
Balogh, Barát, Gerbner， Gyárfás和Sárközy提出了以下猜想。设$G$是一个有$n$顶点的图，其最小度至少为$3n/4$。然后，对于$G$的每$2$边着色，顶点集$V(G)$可以划分为两个顶点不相交的环，每个环一个颜色。
Balogh, Barát, Gerbner, Gyárfás, and Sárközy made the following conjecture. Let $G$ be a graph on $n$ vertices with minimum degree at least $3n/4$. Then for every $2$-edge-colouring of $G$, the vertex set $V(G)$ may be partitioned into two vertex-disjoint cycles, one of each colour.
We prove this conjecture for large $n$, improving approximate results by the aforementioned authors and by DeBiasio and Nelsen.