Chromatic number, clique number, and girth

In this thesis we first consider the relationship between the chromatic number and the clique number in graphs. We examine two constructions of triangle-free graphs with arbitrarily large chromatic number. These constructions are by Mycielski and Erdos and Hajnal. Next, we consider the finite subgraphs of the Erdos-Hajnal graph, which we call Shift Graphs. We represent them as acyclic directed graphs and look at some of their coloring properties. In 1959 Paul Erdos proved the existence of graphs with arbitrarily large girth and arbitrarily large chromatic number. This result had a great impact on different areas of combinatorics, theory of random graphs and chromatic graph theory. In the latter chapters of this paper we discuss the proof and a simplified construction of such graph using hypergraphs.