Name
Abstract | ||
|---|---|---|
Fix r ≥ 2 and a collection of r-uniform hypergraphs $\cal{H}$. What is the minimum number of edges in an $\cal{H}$-free r-uniform hypergraph with chromatic number greater than k? We investigate this question for various $\cal{H}$. Our results include the following: An (r,l)-system is an r-uniform hypergraph with every two edges sharing at most l vertices. For k sufficiently large, there is an (r,l)-system with chromatic number greater than k and number of edges at most c(kr-1 log k)l-(l-1), where $$c=2\left( {100(r)^{2}_{l} \over {l!}}\right)^{1/(l-1)} \left( {10(r-1) \over {l-1}}\right)^{l/(l-1)}.$$This improves on the previous best bounds of Kostochka et al. (Random Structures Algorithms 19 (2001), 87–98). The upper bound is sharp apart from the constant c as shown in (Random Structures Algorithms 19 (2001) 87–98). The minimum number of edges in an r-uniform hypergraph with independent neighborhoods and chromatic number greater than k is of order kr+1-(r-1) log O(1)k as k → ∞. This generalizes (aside from logarithmic factors) a result of Gimbel and Thomassen (Discrete Mathematics 219 (2000), 275–277) for triangle-free graphs. Let T be an r-uniform hypertree of t edges. Then every T-free r-uniform hypergraph has chromatic number at most 2(r - 1)(t - 1) + 1. This generalizes the well-known fact that every T-free graph has chromatic number at most t. Several open problems and conjectures are also posed. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1002/rsa.v36:1 | Random Struct. Algorithms |
Keywords | Field | DocType |
upper bound,hypergraphs | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Hyperbolic tree,Chromatic scale,Upper and lower bounds,Constraint graph,Hypergraph,Logarithm,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 1 | 1042-9832 |
Citations | PageRank | References |
8 | 0.64 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Dhruv Mubayi | 3 | 579 | 73.95 |