Resource title

Partitioning 3-coloured complete graphs into three monochromatic paths

Resource image

image for OpenScout resource :: Partitioning 3-coloured complete graphs into three monochromatic paths

Resource description

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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/41140/

Resource license