turkmath.org

A cocoloring of a graph is a coloring where each color class induces a complete or empty graph. We will introduce the topic of cocolorings and show how the parameter provides a link between Ramsey Theory and traditional graph colorings. Results in these areas tell us something about the difficulty of computing the cochromatic number and provide bounds. Further, we consider some extremal results developed by Paul Erd ̈os and myself and use probabilistic methods to show they are, in some sense, best possible. We will develop some variants on the topic and see a role that probability plays in providing extremal examples.