The Distribution Of Cycle Lengths And Chromatic Number In Graphs

In this thesis,we mainly study the distribution of cycle lengths and chromatic number in graphs.It is organized as follows:In the Introduction,we briefly review the origin and developments of the problems concerning the distribution of cycle lengths in a graph.Some background and main results of our study are presented.In Chapter 2,we introduce some basic definitions and notations in graph theory.We also present some concepts and known results.In Chapter 3,we investigate the connection between cycles of consecutive lengths and chromatic number.First of all,we give a new theorem on A-B paths.In the next part,we prove that for every integer k?3,if G is a 2-connected K3-free graph of minimum degree at least k,then G contains a cycle of length at least 2k+2,except that G=Kk,n for some n?k.In the end,as applications,we consider cycles of consecutive lengths in graphs without a triangle and graphs containing a triangle,respectively.We further discuss cycles of consecutive lengths in graphs of given chromatic number in Chapter 4.To be specific,we prove that for every positive integer k,if G is a graph of chromatic number k+1,then there exists some integer m such that G contains k-1 cycles of lengths 2m+1,2m+2,…,2m+k-1,respectively.This confirms a conjecture of Verstraete.In Chapter 5,we study the chromatic number of graphs without cycles of specific lengths.Let k?3,k>r?0 be two integers and let G be a graph.It is shown that if there is no cycle of length r modulo k in G,then either G is k-colorable,or r=2 and every block of chromatic number at least k+1 in G is the complete graph Kk+1.This answers a question of Moore and West.