Name
Abstract | ||
|---|---|---|
Abstract This paper extends the scenario of the Four Color Theorem in the following way. Let \(\fancyscript{H}_{d,k}\) be the set of all \(k\)-uniform hypergraphs that can be (linearly) embedded into \(\mathbb {R}^d\). We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in \(\fancyscript{H}_{d,k}\). For example, we can prove that for \(d\ge 3\) there are hypergraphs in \(\fancyscript{H}_{2d-3,d}\) on \(n\) vertices whose chromatic number is \(\Omega (\log n/\log \log n)\), whereas the chromatic number for \(n\)-vertex hypergraphs in \(\fancyscript{H}_{d,d}\) is bounded by \({\mathcal {O}}(n^{(d-2)/(d-1)})\) for \(d\ge 3\). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00454-014-9641-2 | Discrete and Computational Geometry |
Keywords | Field | DocType |
Hypergraphs,Coloring,Chromatic number,Embeddings,Four Color Theorem | Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Constraint graph,Four color theorem,Simplicial complex,Omega,Strong coloring,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
52 | 4 | Discrete Comput Geom 52 (2014) 663-679 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carl Georg Heise | 1 | 1 | 0.70 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |
| Oleg Pikhurko | 3 | 318 | 47.03 |
| Anusch Taraz | 4 | 168 | 37.71 |