12123

11109

كارشناسي ارشد

رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1395

نه، [91]ص.: مصور

ص. ع. به فارسي و انگليسي

واژه نامه

1395/11/19

كتابنامه

علوم رياضي

رياضي

ID11109

Topics on Reed s Conjecture Elahe Bakhtiary e bakhtiary@math iut ac ir 2017 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Ramin Javadi rjavadi@cc iut ac ir 2010 MSC 05C15 05C69 Keywords Reed s conjecture Chromatic number clique number AbstractThe chromatic number of a graph G denoted by G is the minimum number of colors requiredto color the vertices of G such that adjacent vertices receive di erent colors In recent decades theconcepts of chromatic number independence number and clique number have been studied widelyin the literature Since the computation of G is NP hard nding bounds for G in terms ofvarious parameters of the given graph G such as clique number G and the maximum degree G has received much attention In this thesis we are going to investigate research studies ona well known conjecture called Reed s Conjecture Let G be a graph of order n with chromaticnumber G maximum degree G and clique number G We know that for every graph G G G G 1 In 1941 Brooks 3 proved that if a connected graph G is neither an oddcycle nor a complete graph then G G This theorem says that if G is a graph with G 3and G G then G G In 26 Reed conjectured that G is bounded above byconvex combinations of the trivial lower bound G and the trivial upper bound G 1 In the G G 1other words he conjectured that G is bounded above by This conjecture 2has not yet been proved for all graphs In this thesis we study the correctness of Reed s conjecturefor some classes of graphs This thesis comes in four chapters All of the required de nitions are explained in Chapter 1 Formore information we consider some simple and basic graphs then verify the Reed s Conjecture forthem In Chapter 2 a vertex partitioning algorithm is explained By the aid of these results theconjecture will be veri ed for some classes of graphs as graphs with independence number 2 graphswith larg maximum degree and some classes of triangle free graphs We survey all these results The

رامين جوادي

بهناز عمومي، غلامرضا اميدي