Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On Planar Mixed Hypergraphs. | On Planar Mixed Hypergraphs Zdenek Dvorak Daniel KraP Department of Applied Mathematics Charles University Malostranské námẽstí 25 118 00 Prague Czech Republic rakdver@ Department of Applied Mathematics and Institute for Theoretical Computer Science Charles University Malostranské némẽstí 25 118 00 Prague Czech Republic kral@ Submitted July 16 2001 Accepted October 12 2001. MR Subject classifications Primary 05C15 Secondary 05C85 68R10 Keywords coloring of hypergraphs planar graphs and hypergraphs mixed hypergraphs algorithms for coloring Abstract A mixed hypergraph H is a triple V C D where V is its vertex set and C and D are families of subsets of V C-edges and D-edges. A mixed hypergraph is a bihypergraph iff C D. A hypergraph is planar if its bipartite incidence graph is planar. A vertex coloring of H is proper if each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The set of all k s for which there exists a proper coloring using exactly k colors is the feasible set of H the feasible set is called gap-free if it is an interval. The minimum maximum number of the feasible set is called a lower upper chromatic number. We prove that the feasible set of any planar mixed hypergraph without edges of size two and with an edge of size at least four is gap-free. We further prove that a planar mixed hypergraph with at most two D-edges of size two is two-colorable. We describe a polynomial-time algorithm to decide whether the lower chromatic number of a planar mixed hypergraph equals two. We prove that it is NP-complete to find the upper chromatic number of a mixed hypergraph even for 3-uniform planar bihypergraphs. In order to prove the latter statement we prove that it is NP-complete to determine whether a planar 3-regular bridgeless graph contains a 2-factor with at least a given number of components. The author acknowledges partial support by GACR 201 1999 0242 and GAUK .
