Decompositions of edge-colored infinite complete graphs into monochromatic paths
Decompositions of edge-colored infinite complete graphs into monochromatic paths
复制标题
将边色无限完全图分解为单色路径
DOI：
10.1016/j.disc.2016.09.028
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Z. Szentmiklóssy
中科院分区：
文献类型：
--
作者：
Márton Elekes;D. Soukup;L. Soukup;Z. Szentmiklóssy
图或超图G=（V，E）的r-边染色是映射c：E→{0，.，r− 1}。推广了Rado的结果，回答了Rado，Gyárfás和Sárközy的问题，证明了：·每个r-边着色的可数无限完全k-一致超图的顶点集都可以划分成r条不同颜色的单色紧路（k-一致超图中的紧路是一系列不同的顶点使得每一组k个连续顶点形成一条边）;·对于所有的自然数r和k，存在一个自然数M，使得每个r-边着色可数无限完全图的顶点集可以被划分为M个单色k次幂的路，这些路是从有限集合中分离出来的（路的k次幂是不同顶点的序列v 0，v 1，.，使得1 ≤ v，.）|i− j|·每个2-边着色可数无限完全图的顶点集可以被划分为4条单色路的正方形，但不一定是3条;·ω 1上的每个2-边着色完全图的顶点集可以被划分为2条不同颜色的单色路。
An r-edge coloring of a graph or hypergraph G=(V, E) is a map c: E→{0,…, r− 1}. Extending results of Rado and answering questions of Rado, Gyárfás and Sárközy we prove that• the vertex set of every r-edge colored countably infinite complete k-uniform hypergraph can be partitioned into r monochromatic tight paths with distinct colors (a tight path in a k-uniform hypergraph is a sequence of distinct vertices such that every set of k consecutive vertices forms an edge);• for all natural numbers r and k there is a natural number M such that the vertex set of every r-edge colored countably infinite complete graph can be partitioned into M monochromatic k th powers of paths apart from a finite set (a k th power of a path is a sequence v 0, v 1,… of distinct vertices such that 1⩽| i− j|⩽ k implies that v i v j is an edge);• the vertex set of every 2-edge colored countably infinite complete graph can be partitioned into 4 monochromatic squares of paths, but not necessarily into 3;• the vertex set of every 2-edge colored complete graph on ω 1 can be partitioned into 2 monochromatic paths with distinct colors.