Vertex Disjoint Cycles And Defective DP-cotorings Of Graphs

Graph Theory is an important branch of Combinatorics,which origi-nates from old mathematical games,such as Euler's Bridges of Koenigsberg Problem and Hamilton's Travel Aroud the Word Game.The famous Four Color Problem inspires the formation and development of Graph Theory.Therefore,cycle problems and coloring problems are two fundamental and classical areas in Graph Theory.In this thesis,we mainly consider degree conditions to guarantee the existence of k vertex disjoint cycles in graphs and digraphs,where k is an arbitrary integer,and defective DP-colorings of sparse multigraphs.We use G and D to denote a graph and a digraph,respectively.For a given graph G,let ?(G)and ?(G)be the minimum and maximum degree of G;for a given vertex x ?(G),let dG(x)be the degree of x in G.Define?t(G)to be the smallest degree sum of all independent t-set of vertices,that is ?t(G):=min{?x?X dG(x):(?)is an independent set of size t},where t?2 is an integer.In graphs and digraphs,we call a cycle of length q a q-cycle;when q=|V(G)|,it is a Hamilton cycle;when q=3,we also call it a triangle.One of the most famous results on cycles is the Dirac Theorem:Every n-vertex graph G with ?(G)? n/2 contains a Hamilton cycle.Since then the research on cycles becomes extensive.We only consider degree conditions to guarantee the existence of k vertex disjoint cycles.In 1963,Corradi and Hajnal find the minimum degree condition to ensure k vertex disjoint cycles.Justesen improves the Corradi-Hajnal Theorem to ?2(G)condition.Later,Enomoto and Wang independently improve the threshold of ?2(G)to 4k-1,which is sharp one.Fujita,Matsumura,Tsugaki,and Yamashita generalize it to ?3(G).A general degree sum condition is conjectured by Gould,Hirohata,and Keller:If G is a graph of sufficiently large order and ?t(G)?(2k-1)t+1,then G contains k vertex disjoint cycles.They prove that their conjecture holds for t=4.In Chapter 2,we solve the conjecture for t>5 by proving:For n>(2t-1)k,every graph G of order n with ?(G)?(2t-1)k+1 contains k vertex disjoint cycles,where k>2 and t>5 are integers.For a given digraph D,we use ?+(D)and ?-(D)to denote the minimum outdegree and indegree of D,respectively.The minimum semidegree ?o(D)of D is the minimum of ?+(D)and ?-(D).We use T to denote a tournament.In digraphs,a path or a cyle is always a directed one.Like the Corradi-Hajanl Theorem,in digraphs there is a famous conjecture of Bermond and Thomassen asserts that every digraph D with ?+(D)?2k-1 contains k vertex disjoint cycles.This conjecture is trivial for k=1.It is proved for k=2 by Thomassen and for k=3 by Lichiardopol,Por,and Sereni.Bang-Jensen,Bessy,and Thomasse prove it for tournaments.The Bermond-Thomassen Conjecture remains open for more than thirty years,which shows that vertex disjoint cycle problems in digraphs are really difficult.Tournaments are special digraphs.There are also many interesting prob-lems on tournaments.In 2010,Lichiardopol conjectures that for q>3 and k?1,every tournament T with ?+(T)?(q-1)k-1 contains k vertex disjoint q-cycles.Lichiardopol proves that his conjecture holds when the minimum semidegree is at least(q-1)k-1,which is a weak version of the conjecture.Zhu proves Lichiardopol's conjecture for q=4.In Chaper 3,we solve Lichiardopol's conjecture for q? 5.In addition,we improve Lichiardopol's theorem:For q?4 and k?1,every tournament T with?o(T)?(q-1)k-1 contains(2-10q-18/3q2-3q-4)k-2q-1 vertex disjoint q-cycles.In particular,every tournament T with ?o(T)?2k-1 contains 16/15k-7 vertex disjoint triangles.Vertex disjoint cycles and colorings have a strong relationship.We all know that a 2-factor of a graph G is a cycle partition of G in a sense.Howev-er,a(di,...,dk)-defective coloring of a graph G is a k-partition V1,V2,...,Vk of V(G),such that ?(G[Vi])?di.Especially,if we let di?2 for every i,then the subgraph G[Vi]consists of vertex disjoint cycles or paths.There-fore,defective colorings and vertex disjoint cycles both belong to partition problems or subgraph problems.We only consider defective DP-colorings with two colors.DP-coloring is a generalization of list coloring developed recently by Dvorak and Postle.It is extended to multigraphs by Bernshteyn,Kostochka and Pron.In Chapter 4,we study(i,j)-defective DP-colorings of sparse multigraphs.An(i,j)-DP-critical multigraph is a multigraph G that has no(i,j)-defective DP-coloring but every proper subgraph of G has such a coloring.Let fDp(i,j,n)be the minimum number of edges that an n-vertex(i,j)-DP-critical multigraph may have.For every i and j,we find linear lower bounds on fDp(i,j,n)that are exact for infinitely many n:All these lower bounds on fDP(i,j,n)are sharp.