Some Results On Cycles And Path-Factors In Graphs And The Studying On Total Coloring Conjecture Of Planar Graphs

All graphs considered in this paper are finite simple graphs. Let G = (V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G, respectively. We use d_G(v) to stand for the degree of v in G. Letâ–³(G) andδ(G) denote the maximum and the minimum vertex degree of G, respectively. For a graph G, |G| = |V(G)| is the order of G, andis the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we defineσ₂ (G) =∞).For a bipartite graph G with partite sets V₁ and V₂, defineδ_1,1(G) = min{d_G(x) + d_G(y)|x∈V₁,y∈V₂},σ_1,1(G) = min{d_G(x) + d_G(y)|x∈V₁,y∈V₂,xy(?)E(G)},(When G is a complete bipartite graph, we defineσ_1,1 =∞). When |V₁| = |V₂|, we call G a balance bipartite graph.For a vertex u of G, the (open) neighborhood, the closed neighborhood of u are denoted by N_G(u) = {x∈V(G)|xu∈E(G)} and N_G[u]={u}∪N_G(u), respectively.The complete bipartite graph K_1,3 is called a claw, and G is said to be claw-free if G has no induced subgraph isomorphic to K_1,3. Let P be a path and C a cycle. We denote the length of P and the length of C by l(P) and l(C), respectively. That is, l(P) = |V(P)| - 1, l(C) = |V(C)|. For any two vertices x and y, the distance from x to y is the length of the shortest path from x to y, denoted by d(x,y). When d(x,y) = 2, we denote A graph G is called quasi-claw-free if J(x, y)≠(?) for each pair of vertices x, y satisfying d(x, y) = 2. Obviously, every claw-free graph is quasi-claw-free, but quasi-claw-free graph may be not claw-free graph. Claw-free graph is a kind of interesting graph, and quasi-claw-free graph is the extending of claw-free graph. Then the results of claw-free graph can be considered in quasi-claw-free graph.A path factor is a spanning subgraph whose components are paths. For a positive integer k, P_≥k-factor means a path factor such that each component has at least k vertices.A Hamilton cycle of G is a cycle of G which contains every vertex of G. A 1-factor of a graph G is a 1-regular spanning subgraph of G, and we call a 1-factor a perfect matching. It is readily seen that a 1-factor of G is a collection of independent edges that covers all vertices of G. A 2-factor of G is a 2-regular spanning subgraph of G. Clearly, each component of a 2-factor of G is a cycle, k independent cycles of G are k cycles which have no common vertex.The independent cycles, 2-factor and path-factor theory in G are important problems in graph factorial theory, also they are the extending of Hamilton cycle theory. It is an interesting problem in graph theory, and it is an international hot topic. The discussion is mature and perfect increasingly. And it is important applications to computer science and network. The study of independent cycles, 2-factor and path-factor theory mostly focus on following: Graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length, Graph containing independent cycles and 2-factor which have specified properties, and path-factor which have specified properties, etc.The paper is divided into four chapters. In Chapter 1, we introduce some basic notations, the history of the cycle theory, and the path-factor, and the progress on the cycle theory, and the path-factor. This chapter is the base of the next two chapters.In Chapter 2, we investigate the graph containing independent cycles which have specified properties. In this chapter, the main results are as the following two theorems.Theorem2.1.1. Suppose k≥2, 1≤s≤k, n≥2k + 1, andThen for any k vertices v₁, V₂,…, v_k, G contains k disjoint cycles C₁, C₂……C_k such that V_i∈V(C_i), |C_i|≤6, and there are at least s 4-cycles in {C₁,C₂,…,C_k}.Theorem2.2.1. Suppose k≥1, 0≤s≤k, n≥2k, andThen for any k vertices v₁,v₂,…,v_k, G contains k disjoint cycles C₁,C₂,…,C_k such that v_i∈V(C_i), |C_i| = 4 for 1≤i≤s, and |C_i|≤6 for s + 1≤i≤k.Concerning the path-factor, Kiyoshi Ando, etc. proved the next result in 2002.Let G be a claw-free graph withδ(G)≥d. Then G has a P_≥d+1-factor.In Chapter 3, we have the following result.Theorem3.1.1. Let G be a quasi-claw-free graph withδ(G)≥d. Then G has a P_≥d+1-factor.In Chapter 4, we discuss some results on coloring theory of graphs. We know that the coloring theory of graphs is another important branch of graph theory. Many kinds coloring of a graph have been studied, such as edge coloring, vertex coloring, face coloring, total coloring, list coloring, star coloring and so on.Given a graph G, an element of G is a member of V(G)∪E(G). Let two elements of a graph G be adjacent if they either adjacent or incident in the traditional sense. Given a graph G, a total k-coloring of G is a function that takes each element to {1,…,k}, such that adjacent distinct elements receive distinct colors. Clearly, no graph has a totalâ–³-coloring. In 1964, Vizing proposed the following conjecture, known as the Total Coloring Conjecture.Every graph has a total (â–³+2)-coloring.The conjecture remains open even for planar graphs. We discuss some results on the Total Coloring Conjecture in Chapter 4, and give the following result.Theorem4.1.1. Every planar graph withâ–³= 6 and has no 5-cycle or 6-cycle has a total 8-coloring.Furthermore, In Chapter 2, Chapter 3 and Chapter 4, we list some problems for future research.