Partitioning 3-coloured complete graphs into three monochromatic paths
Pokrovskiy, Alexey
(2011)
Partitioning 3-coloured complete graphs into three monochromatic paths
Electronic Notes in Discrete Mathematics, 38.
pp. 717-722.
ISSN 1571-0653
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 |
|---|---|
| Keywords | ISI,edge colourings,monochromatic partitions |
| Departments | Mathematics |
| DOI | 10.1016/j.endm.2011.10.020 |
| Date Deposited | 06 Jan 2012 10:08 |
| URI | https://researchonline.lse.ac.uk/id/eprint/41140 |
Explore Further
- http://www.elsevier.com/wps/find/journaldescriptio... (Official URL)