Elekes, Márton and Soukup, Dániel Tamás and Soukup, Lajos and Szentmiklóssy, Zoltán (2017) Decompositions of edge-colored infinite complete graphs into monochromatic paths. DISCRETE MATHEMATICS, 340 (8). pp. 2053-2069. ISSN 0012-365X
|
Text
monopaths150216.pdf Download (263kB) | Preview |
Abstract
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 kth powers of paths apart from a finite set (a kth power of a path is a sequence v0,v1,. of distinct vertices such that 1≤|i-j|≤k implies that vivj 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. . . © 2016 Elsevier B.V.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Uncountable complete graph; Path square; Monochromatic path; Infinite complete graph; Graph partition; Edge coloring; Complete hypergraph |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 21 Nov 2017 09:53 |
Last Modified: | 21 Nov 2017 09:53 |
URI: | http://real.mtak.hu/id/eprint/70250 |
Actions (login required)
![]() |
Edit Item |