Bipartite Matching-extendability Of Series-parallel Graphs And Chromatic Number Of P3(G)

In this paper, we characterize the bipartite matching-extendability of series-parallelgraphs. Motivated by Vizing theory, we also study the chromatic number of P₃(G).The thesis is arranged as follows:Section One is devoted to the introduction of some basic concepts and symbols ingraph theory, current studies in the field of matching-extendability and coloring problem.In Section Two, we study the bipartite matching-extendability of series-parallel graphs,and obtain the following result: A series-parallel graph G is bipartite matching-extendableif and only if it is isomorphic to K₂ or C₄ with multiplicity k≥1.In Section Three, we study the chromatic number of P₃(G). We mainly study thecase when G are some graph classes and obtain the following results: For a triangle-free graph G,χ(P₃(G))≤β(G), whereβ(G) is the vertex covering number of G. Fora connected graph G of order at least 3,χ(P₃(G))≤2 if and only if G is bipartite.Furthermore,χ(P₃(G)) = 1 if and only if G is a star. For a K₄- subdivision graph G,2≤χ(P₃(G))≤3. For a series-parallel graph or an outerplanar graph,χ(P₃(G))≤3.