For a family L (finite or infinite) of oriented graphs, a new parameter called the compressibility Number of L and denoted by z(L) is defined. The main motivation is the application of this parameter in a special case of Turan-type extremal problems for digraphs, in which it replaces the role of chromatic number parameter in the classic extremal problems. Determining this parameter, in the most explicit possible form, for oriented graphs with bounded oriented and/or acyclic chromatic number (planar graph in particular) leads us to the infamous Erdos-Hajnal conjecture.
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact firstname.lastname@example.org.
Member of collection