Premium
Partitioning two‐coloured complete multipartite graphs into monochromatic paths and cycles
Author(s) -
Schaudt Oliver,
Stein Maya
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22424
Subject(s) - combinatorics , mathematics , monochromatic color , multipartite , disjoint sets , bipartite graph , vertex (graph theory) , cograph , partition (number theory) , discrete mathematics , graph , 1 planar graph , chordal graph , physics , quantum mechanics , quantum entanglement , optics , quantum
We show that any complete k ‐partite graph G on n vertices, with k ≥ 3 , whose edges are two‐coloured, can be covered with two vertex‐disjoint monochromatic paths of distinct colours, given 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.