Covering complete partite hypergraphs by monochromatic components
From MaRDI portal
Abstract: A well-known special case of a conjecture attributed to Ryser states that k-partite intersecting hypergraphs have transversals of at most k-1 vertices. An equivalent form was formulated by Gy'arf'as: if the edges of a complete graph K are colored with k colors then the vertex set of K can be covered by at most k-1 sets, each connected in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: Z. Kir'aly proved that in every k-coloring of the edges of the r-uniform complete hypergraph K^r (r >= 3), the vertex set of K^r can be covered by at most sets, each connected in some color. Here we investigate the analogue problem for complete r-uniform r-partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of any color used in the coloring. We propose the following analogue of Ryser conjecture. In every spanning (r+t)-coloring of the edges of a complete r-uniform r-partite hypergraph, the vertex set can be covered by at most t+1 sets, each connected in some color. Our main result is that the conjecture is true for 1 <= t <= r-1. We also prove a slightly weaker result for t >= r, namely that t+2 sets, each connected in some color, are enough to cover the vertex set. To build a bridge between complete r-uniform and complete r-uniform r-partite hypergraphs, we introduce a new notion. A hypergraph is complete r-uniform (r,l)-partite if it has all r-sets that intersect each partite class in at most l vertices. Extending our results achieved for l=1, we prove that for any r >= 3, 2 <= l <= r, k >= 1+r-l, in every spanning k-coloring of the edges of a complete r-uniform (r,l)-partite hypergraph, the vertex set can be covered by at most 1+lfloor frac{k-r+ell-1}{ell}
floor sets, each connected in some color.
Recommendations
- A note on covering edge colored hypergraphs by monochromatic components
- On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
- Monochromatic components in edge-colored complete uniform hypergraphs
- Monochromatic components in edge-colored complete uniform hypergraphs
- Covers in partitioned intersecting hypergraphs
Cites work
- A note on covering edge colored hypergraphs by monochromatic components
- Monochromatic components in edge-colored complete uniform hypergraphs
- Partition of graphs and hypergraphs into monochromatic connected parts
- Vertex coverings by monochromatic cycles and trees
- Vertex covers by monochromatic pieces -- a survey of results and problems
Cited in
(9)- scientific article; zbMATH DE number 15152 (Why is no real title available?)
- A note on covering edge colored hypergraphs by monochromatic components
- Generalizations and strengthenings of Ryser's conjecture
- Partition of graphs and hypergraphs into monochromatic connected parts
- scientific article; zbMATH DE number 524129 (Why is no real title available?)
- Rainbow \(H\)-factors of complete \(s\)-uniform \(r\)-partite hypergraphs
- Monochromatic components in edge-colored complete uniform hypergraphs
- On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
- Partial covering of hypergraphs
This page was built for publication: Covering complete partite hypergraphs by monochromatic components
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2404363)
