Extremal Colorings and Extremal Satisfiability : An Interplay between Combinatorics and Complexity Theory

Combinatorial problems are often easy to state and hard to solve. A whole bunch of graph coloring problems falls into this class as well as the satisfiability problem. The classical coloring problems consider colorings of objects such that two objects which are in a relation receive different colors, e.g., proper vertex-colorings, proper edge-colorings, or proper face-colorings of plane graphs. A generalization is to color the objects such that some predefined patterns are not monochromatic. Ramsey theory deals with questions under what conditions such colorings can occur. A more restrictive version of colorings forces some substructures to be polychromatic, i.e., to receive all colors used in the coloring at least once. Also a true-false-assignment to the boolean variables of a formula can be seen as a 2-coloring of the literals where there are restrictions that complementary literals receive different colors.