On 2-coloring certain \(k\)-uniform hypergraphs (Q1865419): Difference between revisions

Some sufficient conditions for the existence of a \(2\)-colouring of \(k\)-uniform hypergraphs are presented. When the number of edges of a hypergraph \(H\) equals to the number of elements of the base set of \(H\), the conditions are connected with properties of the permanent of the incidence matrix of \(H\). The used method of proof was already described by \textit{A. Noga} in [Comb. Probab. Comput. 8, 7-29 (1999; Zbl 0920.05026)]. In the general case, the sufficient condition is related to the number of quasi-matchings in an associated graph.