Partitioning 3-coloured complete graphs into three monochromatic paths
Pokrovskiy, A.
(2011).
Partitioning 3-coloured complete graphs into three monochromatic paths.
Electronic Notes in Discrete Mathematics,
38, 717-722.
https://doi.org/10.1016/j.endm.2011.10.020
In this paper we show that in any edge-colouring of the complete graph by three colours, it is possible to cover all the vertices by three disjoint monochromatic paths. This solves a particular case of a conjecture of Gyárfás. As an intermediate result, we show that in any edge colouring of the complete graph by two colours, it is possible to cover all the vertices by a monochromatic path and a disjoint monochromatic balanced complete bipartite graph.
| Item Type | Article |
|---|---|
| Copyright holders | © 2011 Elsevier |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.endm.2011.10.020 |
| Date Deposited | 06 Jan 2012 |
| URI | https://researchonline.lse.ac.uk/id/eprint/41140 |
Explore Further
- https://www.scopus.com/pages/publications/82955171688 (Scopus publication)
- http://www.elsevier.com/wps/find/journaldescriptio... (Official URL)