Monochromatic partitions of complete uniform hypergraphs

DOI10.1137/S0895480199357716MaRDI QIDQ2719171zbMATH OpenOpenAlexFDO

Authors Krzysztof Bryś, Zbigniew Lonc

Publication date 21 June 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480199357716

zbMATH Keywords

complete uniform hypergraphscomputationally complexityRamsey theoremvertex partition

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Review text

Let \(H\) be a \(c\)-(vertex)-colored \(n\)-uniform complete hypergraph. The problem \(P_{n,c,k}\) is to decide whether \(H\) can be partitioned into monochromatic subhypergraphs of order at least \(k\) (where all numbers are fixed positive integers). The main result of this paper is that this problem is polynomial time solvable. The same problem for graphs and for two colors was widely studied earlier.

Recommendations

• Monochromatic path and cycle partitions in hypergraphs
• Monochromatic loose-cycle partitions in hypergraphs
• Partitioning edge-colored hypergraphs into few monochromatic tight cycles
• Partitioning 2-coloured complete \(k\)-uniform hypergraphs into monochromatic \(\ell\)-cycles
• scientific article; zbMATH DE number 568840

Cited in

(1)

• NP-hard and linear variants of hypergraph partitioning

This page was built for publication: Monochromatic partitions of complete uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719171)