Coloring d-embeddable k-uniform hypergraphs

Publikationstyp
Journal Article
Date Issued
2014-10-17
Sprache
English
Author(s)
Heise, Carl Georg  
Panagiotou, Konstantinos  
Pikhurko, Oleg  
Taraz, Anusch  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/9901
Journal
Discrete & computational geometry  
Volume
52
Issue
4
Start Page
663
End Page
679
Citation
Discrete and Computational Geometry 52 (4): 663-679 (2014)
Publisher DOI
10.1007/s00454-014-9641-2
Scopus ID
2-s2.0-84911415232
Publisher
Springer
This paper extends the scenario of the Four Color Theorem in the following way. Let Hd,k be the set of all k-uniform hypergraphs that can be (linearly) embedded into Rd. We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in Hd,k. For example, we can prove that for (Formula presented.) there are hypergraphs in H2d-3,d on n vertices whose chromatic number is Ω(log n/log log n), whereas the chromatic number for n-vertex hypergraphs in Hd,d is bounded by (Formula presented.).
Subjects
Chromatic number
Coloring
Embeddings
Four Color Theorem
Hypergraphs
DDC Class
510: Mathematik