On planar mixed hypergraphs
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\).
- scientific article; zbMATH DE number 1869704
- Colouring planar mixed hypergraphs
- On feasible sets of mixed hypergraphs
- The smallest 3-uniform bi-hypergraph which is a realization of a given vector
- scientific article; zbMATH DE number 1696541
- 3-Colorability of plane hypergraphs
- scientific article; zbMATH DE number 5296053
- A note on the colorability of mixed hypergraph using \(k\) colors
- Mixed colorings of hypergraphs
- More result on the smallest one-realization of a given set
- Mixing 3-colourings in bipartite graphs
- On maximum face-constrained coloring of plane graphs with no short face cycles.
- Colouring planar mixed hypergraphs
- On the upper chromatic number of (v₃,b₂)-configurations
- Chords of 2-factors in planar cubic bridgeless graphs
- Facially-constrained colorings of plane graphs: a survey
- Coloring mixed hypertrees
- scientific article; zbMATH DE number 4047771 (Why is no real title available?)
- 3-Colorability of plane hypergraphs
- scientific article; zbMATH DE number 4072998 (Why is no real title available?)
- Non-monochromatic non-rainbow colourings of -hypergraphs
- scientific article; zbMATH DE number 1491627 (Why is no real title available?)
- scientific article; zbMATH DE number 1839477 (Why is no real title available?)
- Mixed hypergraphs and beyond
- WORM colorings of planar graphs
- scientific article; zbMATH DE number 6438474 (Why is no real title available?)
- On planar mixed hypergraphs
- Coloring face hypergraphs on surfaces
This page was built for publication: On planar mixed hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5948492)
