Extremal oriented graphs and Erdös-Hajnal conjecture

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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 statement
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 summit-permissions@sfu.ca.
Scholarly level
Member of collection
Attachment Size
ETD4568.pdf 290.9 KB