Menu
The following partition problem was first introduced by R.C. Entringer and has subsequently been studied by the first author and more recently by Bollobas and Scott, who consider the hypergraph version as well, using a probabilistic technique. The partition problem is that of coloring the vertex set of a graph with \(s\) colors so that the number of induced edges is bounded for each color class. The techniques employed are non-constructive and non-probabilistic and improve the known bounds in the previous papers.