Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II. (English) Zbl 1375.05108
Summary: We prove that given an edge colouring of an infinite complete graph with finitely many colours, one can partition the vertices of the graph into disjoint monochromatic paths of different colours. This answers a question of R. Rado [Ann. Discrete Math. 3, 191–194 (1978; Zbl 0388.05031)].
For Part I see [M. Elekes et al., Discrete Math. 340, No. 8, 2053–2069 (2017; Zbl 1362.05102)].
For Part I see [M. Elekes et al., Discrete Math. 340, No. 8, 2053–2069 (2017; Zbl 1362.05102)].
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
disjoint monochromatic pathsReferences:
| [1] | M. Elekes, D. T. Soukup, L. Soukup, and Z. Szentmiklssy, Decompositions of edge-colored infinite complete graphs into monochromatic paths, Discrete Mathematics 340 (2017), 2053-2069. · Zbl 1362.05102 · doi:10.1016/j.disc.2016.09.028 |
| [2] | P. Erds, A. Gyárfás and L. Pyber, Vertex coverings by monochromatic cycles and trees, Journal of Combinatorial Theory, Series B 51 (1991), no. 1, 90-95. · Zbl 0766.05062 · doi:10.1016/0095-8956(91)90007-7 |
| [3] | Gyárfás, A., Covering complete graphs by monochromatic paths, 89-91 (1989), Berlin · Zbl 0736.05062 · doi:10.1007/978-3-642-61324-1_7 |
| [4] | A. Gyárfás, M. Ruszinkó, G. N. Sárközy, and E. Szemerédi, An improved bound for the monochromatic cycle partition number, Journal of Combinatorial Theory, Series B 96 (2006), no. 6, 855-873. · Zbl 1115.05031 · doi:10.1016/j.jctb.2006.02.007 |
| [5] | A. Gyárfás and G. N. Sárközy, Monochromatic path and cycle partitions in hypergraphs, The Electronic Journal of Combinatorics 20 (2013), no. 1, P18. · Zbl 1266.05091 |
| [6] | Hajnal, A.; Komjáth, P.; Soukup, L.; Szalkai, I., Decompositions of edge colored infinite complete graphs, 277-280 (1987), Amsterdam · Zbl 0697.05028 |
| [7] | Kunen, K., Set Theory. An Introduction to Independence Proofs (1980), Amsterdam-New York · Zbl 0443.03021 |
| [8] | A. Pokrovskiy, Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory, Series B 106 (2014), 70-97. · Zbl 1300.05260 · doi:10.1016/j.jctb.2014.01.003 |
| [9] | R. Rado, Monochromatic paths in graphs, Ann. Discrete Math. 3 (1978), 191-194. · Zbl 0388.05031 · doi:10.1016/S0167-5060(08)70507-7 |
| [10] | D. T. Soukup, Colouring problems of Erds and Rado on infinite graphs, PhD thesis, University of Toronto, Department of Mathematics (2015). |
| [11] | L. Soukup, Elementary submodels in infinite combinatorics, Discrete Math. 311 (2011), no. 15, 1585-1598. · Zbl 1408.05110 · doi:10.1016/j.disc.2011.01.025 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
