file.pdf (187.77 kB)
Download file

Coloring H-free hypergraphs

Download (187.77 kB)
journal contribution
posted on 26.02.2008, 00:00 by Tom Bohman, Alan FriezeAlan Frieze, Dhruv Mubayi

Fix r ≥ 2 and a collection of r-uniform hypergraphs . What is the minimum number of edges in an -free r-uniform hypergraph with chromatic number greater than k? We investigate this question for various . 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

    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.

History

Publisher Statement

This is the accepted version of the article which has been published by Wiley in final form at http://dx.doi.org/10.1002/rsa.20298

Date

26/02/2008

Usage metrics

Exports