A Narrative Study in Ramsey Graph Theory using Rank Coloring

Now a day’s Graph Ramsey Theory has grown to one of the most familiar active areas. A major impetus behind the early development of Graph Ramsey Theory was the hope that it would eventually lead to methods for determining larger values of the classical Ramsey number R (m ,n).In fact, it is probably safe to say that the results arising from Graph Ramsey Theory will prove to be more valuable and interesting than knowing the exact values of R(m ,n).This paper deals with the construction of extremal graphs. it is divided into three major areas: i) Ramsey numbers with Turan’s theorem ii) Rank coloring with graph. First once called Ramsey numbers. For the classical Ramsey numbers. G is taken to be a complete graph. We begin by giving Ramsey theorem which gives a recurrence relation for r(k,1), k>=2 and 1>=2.The existence of r (k1,k2…….km) is guaranteed by Ramsey’s original theorem. Ramsey theorem yields an upper bound for r(k,1). Erdos’s theorem (1947) yields a lower bound for r(k,k).it deals with Turan’s theorem and some of its consequences. Turan’s theorem gives upper bounds for the number of edges of graphs with certain specified properties.The study of Ramsey has become important since cubic graphs play a vital role in several situations in graph theory, as for instance, in the four color problem. Finally called Rank coloring graph, A ranking of a graph is a coloring of the vertex set with positive integers such that on every path connecting two vertices of the same color there is a vertex of larger color. We show that the ranking number of a directed graph is bounded by that of its longest directed path plus one, and that it can be computed in polynomial time.