Three-coloring three-dimensional uniform hypergraphs
We study the chromatic number of hypergraphs whose vertex-hyperedge incidence poset has dimension at most three. Schnyder (1989) showed that graphs with this property are planar and thus four-colorable. Results of Keszegh and Pálvölgyi (2015) imply that k-uniform hypergraphs with dimension at most three are twocolorable for k≥9. In this paper we show that kuniform hypergraphs with dimension at most three are three-colorable for k ≥ 6. This implies three colorability of k-uniform triangle Delaunay hypergraphs and kuniform hypergraphs induced by points and octants in 3-space. We also observe that the chromatic number of k-uniform hypergraphs with dimension d ≥4 is not bounded by any function of k and d.
|Conference||31st Canadian Conference on Computational Geometry, CCCG 2019|
Biniaz, A. (Ahmad), Bose, P, Cardinal, J. (Jean), & Payne, M.S. (Michael S.). (2019). Three-coloring three-dimensional uniform hypergraphs. In Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019 (pp. 23–28).