Publication:324825

DOI10.1016/J.ENDM.2015.07.052zbMath1347.05160arXiv1407.5083OpenAlexW2964348291WikidataQ128892494 ScholiaQ128892494MaRDI QIDQ324825

Oliver Schaudt, Maya Jakobine Stein

Publication date: 17 October 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We show that any complete $k$-partite graph $G$ on $n$ vertices, with $k ge 3$, whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distinct colours. We prove this under the necessary assumption that the largest partition class of $G$ contains at most $n/2$ vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but $o(n)$ vertices of the graph can be covered with two vertex-disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex-disjoint monochromatic cycles.

Full work available at URL: https://arxiv.org/abs/1407.5083

zbMATH Keywords

monochromatic cycle partitionmonochromatic path partitiontwo-coloured graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Cites Work

• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning 3-colored complete graphs into three monochromatic cycles
• An improved bound for the monochromatic cycle partition number
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Vertex coverings by monochromatic cycles and trees
• Partitioning complete bipartite graphs by monochromatic cycles
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (7)

Vertex covers by monochromatic pieces -- a survey of results and problems ⋮ Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles ⋮ Vertex covering with monochromatic pieces of few colours ⋮ Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles ⋮ The complexity for partitioning graphs by monochromatic trees, cycles and paths ⋮ Local colourings and monochromatic partitions in complete bipartite graphs ⋮ Almost Partitioning a 3-Edge-Colored $K_{n,n}$ into Five Monochromatic Cycles

This page was built for publication: Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles