On planar mixed hypergraphs (Q5948492)

A mixed hypergraph consists of a vertex set \(V\), together with edges (that is subsets of vertices) which may be of type \(B\), \(C\) or \(D\). In a coloring of the vertices of a mixed hypergraph it is required that every edge of type \(C\) (\(D\)) has two vertices with a common color (with different colors), whereas edges of type \(B\) must meet both of these requirements. A mixed hypergraph in which every edge is of type \(B\) is a bihypergraph. A hypergraph is planar if its bipartite incidence graph is planar. NEWLINENEWLINENEWLINEIt is shown here that it can be determined in polynomial time if a planar mixed hypergraph has a 2-coloring, but it is NP-complete to determine if it has a 3-coloring. Furthermore it is proved that it is NP-complete to determine if a \(3\)-uniform planar bihypergraph has a \(k\)-coloring, where \(k\) is part of the input. The latter is established by showing that it is NP-complete to determine if a bridgeless 3-regular planar graph has a 2-factor with at least \(k\) components, where \(k\) is part of the input. The same questions with \(k\) fixed remain open.NEWLINENEWLINENEWLINEAnother nice result obtained here is that planar mixed hypergraphs without edges of size 2 and with at least one edge of size at least 4, have a gap-free spectrum: the existence of colorings using \(k_1\) and \(k_2\) colors respectively, forces the existence of a \(k\)-coloring for every \(k_1\leq k\leq k_2\). Combining a recent result of \textit{A. A. Diwan} [J. Comb. Theory, Ser. B 84, 249-259 (2002; Zbl 1029.05123)] with results of \textit{A. Kündgen, E. Mendelsohn} and \textit{V. Voloshin} [Electron. J. Comb. 7, Research paper R60 (2000; Zbl 0978.05027)] it can be shown that this result holds even if there is no edge of size \(\geq 4\).