Chromatic capacities of graphs and hypergraphs Original Research Article

Given a hypergraph H, the chromatic capacity χ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 χ and chromatic capacity χcap, then χcap>(1−o(1)) χ/2n ln χ, extending a result of Brightwell and Kohayakawa. We also answer a question of Archer by constructing, for all r and χ, r-uniform hypergraphs attaining the bound χcap=χ−1. Finally, we show that a connected graph G has χ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.