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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Partition of graphs and hypergraphs into monochromatic connected parts
scientific article

    Statements

    Partition of graphs and hypergraphs into monochromatic connected parts (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    24 October 2012
    0 references
    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.
    0 references
    covering of edge colored graphs by monochromatic connected parts
    0 references

    Identifiers