مسيرها و دورهاي تك رنگ در گراف هاي 2- رنگ آميزي يالي چگال

چكيده انگليسي :

Monochromatic Cycles and Paths in 2 edge Coloured Dense Graphs Ameneh Nejadshakhi a nejadshakhi@math iut ac ir June 30 2019 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Gholamreza Omidi romidi@cc iut ac ir2010 MSC 05C55 05D10 Keywords Dense Ramsey Number Abstract This M Sc thesis is based on the following papers G N Star versus two stripes Ramsey numbers and a conjecture of Schelp Combi G A S natorics Probability and Computing 21 2012 179 186 G N Ramsey number of paths and connected matchings in Ore B J G A L J S type host graphs Discrete Mathematics 339 2016 1690 1698 M Monochromatic cycles in 2 coloured B F S T S A S J W graphs Combinatorics Probability and Computing 21 2012 57 87A graph G is a triple consisting of a vertex set V G an edge set E G and a relation which associates each ofthe edges with two vertices called it s endpoints A complete graph is a simple graph whose vertices are pairwiseadjacent the complete graph with n vertices is denoted Kn Graphs with a number of edges roughly quadratic intheir number of vertices are usually called dense In 1928 the English mathematician Frank Plumpton Ramsey published his paper on a problem of formal logic inwhich he proved what would become known as Ramsey s Theorem The paper has led to a large area of combinatoricsnow known as Ramsey Theory To understand Ramsey s Theorem and Ramsey Numbers we must first understand what is meant by colored graph A2 coloured graph is a graph whose edges have been colored with 2 different colors The Ramsey number of a simplegraph G is the least integer n such that every 2 edge coloring of Kn yields a monochromatic copy of G This numberis denoted by R G G The existence of these numbers was first proven by Ramsey and rediscovered independently by Erd s and Szekeres Determininig or estimating Ramsey numbers is one of the central problems in combinatorics The path path Ramsey number was determined by Gy rf s and Gerencs r in 1967 and its diagonal case stated forconvenience for even paths is that R P2n P2n 3n 1 i e in every 2 colouring of the edges of K3n 1 thecomplete graph on 3n 1 vertices there is a monochromatic P2n a path on 2n vertices It is a natural question to ask whether a similar conclusion is true if K3n 1 is replaced by some subgraph of it R H Schelp conjectured that if G is a graph with V G R Pn Pn such that G 3 V G 4 then inevery 2 colouring of the edges of G there is a monochromatic Pn In other words the Ramsey number of a path doesnot change if the graph to be colored is not complete but has a large minimum degree The main focus of the thesis is to demonstrate asymptotic version of conjecture for paths In fact we examine the resultsobtained by Gy rf s and S rk zy In 2012 Benevides and his colleagues showed that graph G with G 3n 4has a monochromatic cycle at least 2 3 o 1 n And In 2016 Bar t and his colleagues suggested the followingstronger conjecture allowing host graphs with the corresponding Ore type condition If G is a graph on 3n 1vertices such that for any two non adjacent vertices u and v dG u dG v 3 3n 1 then in any 2 coloring 4of the edges of G there is a monochromatic path on 2n vertices Our main objective in this thesis is to look at theresults obtained in conjunction with schelp s conjecture

نژادشاخي، آمنه

مسيرها و دورهاي تك رنگ در گراف هاي 2- رنگ آميزي يالي چگال

اعداد رمزي , تطابق , گراف هاي چگال