Random Structures & Algorithms

List colorings of multipartite hypergraphs

Early View

Let χl(G) denote the list chromatic number of the r‐uniform hypergraph G. Extending a result of Alon for graphs, Saxton and the second author used the method of containers to prove that, if G is simple and d‐regular, then . To see how close this inequality is to best possible, we examine χl(G) when G is a random r‐partite hypergraph with n vertices in each class. The value when r = 2 was determined by Alon and Krivelevich; here we show that almost surely, where d is the expected average degree of G and . The function g(r,α) is defined in terms of “preference orders” and can be determined fairly explicitly. This is enough to show that the container method gives an optimal lower bound on χl(G) for r = 2 and r = 3, but, perhaps surprisingly, apparently not for r ≥ 4.

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.