extremal coloring

In general, an extremal graph is the largest graph of order n which does not contain a given graph G as a subgraph. Turán studied extremal graphs that do not contain a complete graph K_p as a subgraph. One much-studied type of extremal graph is a two-coloring of a complete graph K_n of n nodes which contains exactly the number N congruent (R + B)_min of monochromatic forced triangles and no more (i.e., a minimum of R + B where R and B are the numbers of red and blue triangles).

bichromatic graph | blue-empty graph | extremal graph theory | Goodman's formula | monochromatic forced triangle | Schwenk's formula | Turán graph