Balanced Independent Sets and Colorings of Hypergraphs

ABSTRACT

A ‐uniform hypergraph is ‐partite if can be partitioned into sets such that every edge in contains precisely one vertex from each . We call such a graph ‐balanced if for each . An independent set in is balanced if for each , and a coloring is balanced if each color class induces a balanced independent set in . In this paper, we provide a lower bound on the balanced independence number in terms of the average degree , and an upper bound on the balanced chromatic number in terms of the maximum degree . Our results recover those of recent work of Chakraborti for .