Chromatic capacities of graphs and hypergraphs

Given a hypergraph H, the chromatic capacity chi(cap)(H) of H is the largest k for which there exists a k-coloring of the edges of H such that, for every coloring of the vertices of H with the edge colors, there exists an edge that has the same color as all its vertices. We prove that if G is a graph on n vertices with chromatic number chi and chromatic capacity chi(cap), then chi(cap) > (1 - o(1)) chi/root2n ln chi, extending a result of Brightwell and Kohayakawa. We also answer a question of Archer by constructing, for all r and chi, r-uniform hypergraphs attaining the bound chi(cap) = chi - 1. Finally, we show that a connected graph G has chi(cap) (G)= 1 if and only if it is almost bipartite. In proving this result, we also obtain a structural characterization of such graphs in terms of forbidden subgraphs. (C) 2003 Published by Elsevier B.V.