Partition of graphs and hypergraphs into monochromatic connected parts (Q456358)

Summary: We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any 2-edge-colored non-trivial \(r\)-uniform hypergraph \(H\), the vertex set can be partitioned into at most \(\alpha (H)-r+2\) monochromatic connected parts, where \(\alpha (H)\) is the maximum number of vertices that does not contain any edge. In particular, any 2-edge-colored graph \(G\) can be partitioned into \(\alpha(G)\) monochromatic connected parts, where \(\alpha (G)\) denotes the independence number of \(G\). This extends König's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without 3-edge-colored triangles. We show that for any Gallai-coloring of a graph \(G\), the vertex set of \(G\) can be partitioned into monochromatic connected parts, where the number of parts depends only on \(\alpha(G)\). This extends its cover-version proved earlier by Simonyi and two of the authors.