The Extremal Problems On The Potentially κ-partite Graphs

Given a simple graph G,let V(G)={v₁,v₂,…,v_n} be the vertex set of G, and let di be the degree of v_i,i=1,2,…,n,and d₁≥d₂≥…≥d_n.ThenÏ€=(d₁,…,d_n) is called the degree sequence of G.LetÏ€=(d₁,…,d_n) be a non-increasing nonnegative integer sequence,Ï€is said to be graphic if it is the degree sequence of a simple graph G and G is called a realization ofÏ€.For given a graph H,a graphic sequenceÏ€=(d₁,d₂,…,d_n) is said to be potentially Hgraphic if there exists a realization ofÏ€containing H as a subgraph.Let K_k,C_k and P_k denote a complete graph on k vertices,a cycle on k vertices and a path on k+1 vertices,respectively.K_p,q,K_p,q,r,K_p,q,s,t denote complete bipartite graphic, complete 3-partite graphic,complete 4-partite graphic.This thesis mainly consider the extremal problems on potentially k-partite graphic sequences.The following results are obtained in this thesis:1,We characterize the potentially K_2,3-e-graphic sequences.2,The extremal problems on the potentially K_2,2.1,1-graphic sequences are given.