On Chromatic Number Of Graphs Without Certain Induced Subgraphs

In general, there is no upper bound on the chromatic number of a graph Gin terms of its clique number, since by a classical result of Erod(o|")s we know thatthe difference X(G)-ω(G) can be arbitrarily large, where X(G),ω(G) denotechromatic number and clique number of G respectively. In this thesis, we shallfocus on some properties of (?)-free graphs and obtain results that the chromaticnumber of (?)-free graphs has upper bound in terms of their clique number, where(?) is a set of graphs of order four or five.In section one, we introduce the background and terminologies.Section two presents some results concerning (2K₁+K₂)-free graphs. Gyárfáshas showed that chromatic number of (2K₁+K₂)-free graphs has no linear upperbound in terms of their clique number. Accordingly, we study {2K₁+K₂, C₅}-free graphs and {2K₁+K₂, C₄}-free graphs. The following results are obtained.If G is a {2K₁+K₂, C₅}-free graph, then X(G)=ω(G) forω(G)=2 andX(G)≤2ω(G)^3/2 forω(G)≥3. As a corollary of above result, we obtain that ifthe graph G contains no induced 5-cycle and induced kK₁+K₂ for an integerk≥2, then X(G)≤2ω^k-1ω^1/2. Moreover, we give the structural characterizationof {2K₁+K₂, C₄}-free graphs. If G is a {2K₁+K₂, C₄}-free graph, we show thatifα(G)＞3 then G is a split graph, and ifα(G)=3 then for any independentset S of cardinality 3, G-S is a chordal graph or G-S(?)C₆∨K_n-9.At last of section two, we introduce the concept of divisibility. A k-divisionof a graph G=(V, E) is a partition of the vertex set V into k sets V₁,…,V_ksuch that no V_i (i=1,…,k) contains a clique ofω(G). And we call agraph G k-divisible if each induced subgraph H of G with at least one edgehas a k-division. Gravier, Hoāng and Maffray showed that every (2K₁+K₂)-free graph is 3-divisible. But we are interested in particular in the 2-divisiblecase. Accordingly, in section two, we show that a {2K₁+K₂, C₅}-free graph is2-divisible.Let R(p, q) be the Ramsey function. It was showed that for a (K₁+P₃)- free graph G, X(G)≥R(3,ω+1)-1/2 In section three, we give some results about(K₁+P₃)-free graph. The following result is obtained: if G is a {K₁+P₃, C₄}-freegraph then X(G)=ω(G) forα(G)≥3, and X(G)≤2ω(G) forα(G)=2.