Browsing by Author "2c55523a-9b90-4986-a4dd-03e4f9905712"

Now showing items 1-3 of 3

    • Almost partitioning A 3-edge-colored Kn,n into five monochromatic cycles 
      Lang, Richard; Schaudt, Oliver; Stein, Maya (Society for Industrial and Applied Mathematics Publications, 2017)
      We show that for any coloring of the edges of the complete bipartite graph Kn,n with three colors there are five disjoint monochromatic cycles which together cover all but o(n) of the vertices. In the same situation, 18 ...
    • Approximately coloring graphs without long induced paths 
      Chudnovsky, Maria; Schaudt, Oliver; Spirkl, Sophie; Stein, Maya; Zhong, Mingxian (Springer, 2017)
      It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable ...
    • Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles 
      Schaudt, Oliver; Stein, Maya (Wiley-Liss Inc., 2019)
      © 2018 Wiley Periodicals, Inc. 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 ...