Disable Subgraph And Coloring Problem Studies

Graph coloring theory not only plays an important role in graph theory,but also has a wide range of practical applications.Scheduling problems of all kinds,and sorting problems can basically be boiled down to coloring problems.Jense and Toft assert that graph coloring theory is central to discrete mathematics.The vertex coloring problem is always the most classical problem in graph coloring theory.This paper mainly discusses the vertex coloring problem with forbidden subgraphs.Let ?(G)and ?(G)represent the chromatic number and clique number of G,respectively.In 1975,Gyárfás[31]put forward the concept of ?-bounded class.Let g be a family of graphs.If there is a function f such that for any G E g,?(G)?f(?(G)),then g is called a ?-bounded class,and f is called a binding-function of g.One of the important problems is to study which family of graphs can be X-bounded,and find the optimal binding function for X-bounded graph class.Since the clique number is the trivial lower bound of chromatic number,if a family of X-bounded graphs has a linear binding function,from the asymptotic point of view,the linear function must be the optimal binding function of this family.Let G[S]denote the subgraph of G induced by a subset S of V(G),where S is the vertex set of G[S],and for u,v ? S,uv ? E(G[S])if and only if uv ? E(G).Given graph H,G is called H-free if G does not induce H.Analogously,for a family of graphs F,G is F-free if G induces no graph of F.Given graph G,if there is a map:?:E(G)? {0,1} such that for any hole or triangle H,?e?E(H)?(e)is odd,then we say that G is an odd signable graph.An induced cycle with length at least 4 is called a hole,and is called an even hole if the cycle has an even length.Obviously,by giving weight 1 to each edge,it is easy to see that every even-hole-free graph is an odd signable graph.That is,even-hole-free graphs belong to the class of odd signable graphs.A cap is obtained from a hole by adding a new vertex and joining it to exactly two adjacent vertices of the hole.The relationship among the even-hole-free graphs,the Berge graphs with the ?perfect graphs led it to be investigated.Reed proves that if G is(even hole,triangle)free,then ?(G)?3,that is,the binding function of this kind of graphs is 3.Kloks et al[39]prove that if G is(even hole,K4-e)-free,then ?(G)?3,where K4-e is the graph obtained from K4 by removing an edge.In 2018,Cameron et al[8]proved that the binding function of(even hole,cap)-free graphs is[3?(G)/2].and they questioned whether this kind of graph satisfies x(G)?[5?(G)/4].Cameron et al[8]make a decomposition on(4-hole,cap)-free odd signable graphs and find a clique path(where every vertex of the path is a clique).Due to the limitation of ?(G),it is obvious that there is a vertex of the path whose degree is at most[3?(G)/2]-1.then by the greedy algorithm,it is known that the(4-hole,cap)-free odd signable graphs are[3?(G)/2]-colorable.To study Cameron et al's question,we may choose a minimum counterexample.Since the class of(even hole,cap)-free graphs is a subset of the class of(4-hole,cap)free odd signable graphs,the structure decomposition theorem of the(4-hole,cap)free odd signable graphs is also applicable to the(even hole,cap)-free graphs.We can find a clique path in the minimum counterexample G where every other vertex except the clique path has been colored properly.According to the size of the two end clique vertices of the clique path,we constantly adjust the way of coloring so that all vertices on the clique path except a certain clique vertex have been colored properly.In addition,the same coloring should be used as much as possible between two clique vertices that are complete to this certain clique vertex,then this certain clique vertex can also be colored properly,thus leading to contradiction.Cameron et al[8]just analyzed the structure of this kind graphs,and obtained their upper bound according to its structural characteristics.On the basis of decomposing its structure,according to the size of the clique vertices,we continuously adjust the way of coloring to carry out color expansion.In Chapter 2,we show that if G is an(even hole,cap)-free graph,then its chromatic number is at most[4?(G)/3];and use the same method as above,we prove that if G further has no 5-cycles sharing exactly one edge,then ?(G)?[5?(G)/4].We reduce the constant from 3/2 to 4/3,and by forbidding a certain class of graphs,we can reduce the constant to 5/4.In 2008,Berry,Chudnovsky,Havet,Reed and Seymour[1]confirmed a conjecture of Reed[47],and proved that each even hole-free graph has a vertex whose neighboring set is composed of two cliques.Then,according to the greedy algorithm,each even hole-free graph is(2?(G)-1)-colorable.Recently,Chudnovsky and Seymour[18]fixed the flaw in[1]and reprove this conclusion.In[18],Chudnovsky and Seymour believe that the Theorem 3.1.2(1)in[1]should still be true and that the proof of the Theorem 3.1.2 excludes many odd signable graphs.Addario-Berry et al[1]give an example,a cube,to show that the Theorem 3.1.2 is not valid on the class of odd signable graphs.Note that there are many 4-holes in the cube,we think that there should also be a conclusion similar to the Theorem 3.1.2 of[1]on the class of 4-hole-free odd signable graphs.In fact,the structural decomposition theorem of even-hole-free graphs proved by Conforti,Cornuejols,Kapoor and Vuskovic[21]is also applicable to the 4-hole-free odd signable graphs.We use NS(u)to represent the neighbourset of u in S,and use N(S)to represent the set of vertices consisting of S itself and their neighbours where S is a subset of V(G).If N(S)=V(G),then S is said to be a dominating set of G.Let H=h1h2…hkh1 be a hole of G and c1,c2 ? V(G-H),c1c2 ? E(G)and NH(C1)=NH(c2)={h1,h2}.Assume that there exists i ? {2,3,...,k-1}and c1hi-path P1,c2hi+1-path P2 where |P1|=|P2|=2 such that and are anticomplete to H and c1P1hihi+1P2c2 is a 6-hole.We use A to denote G[V(H)U V(P1)? V(P2)],where P1*and P2*are the sets containing internal vertices of P1 and P2,respectively.A-free excludes some 6-hole,then even-hole-free graphs belong to the class of(4-hole,A)-free odd signable graphs.In Chapter 3,we study the class of(4-hole,A)free odd signable graphs.By constantly using the properties of odd signable graphs,we prove the following conclusions:Let G be a(4-hole,A)-free odd signable graphs,K is a nondominating clique with |K|?2.Assuming G contains no nondominating holes,then there exists a vertex in V(G)\N(K)whose neighbour set consists of two cliques.As a corollary,for any(4-hole,A)-free odd signable graph,if |V(G)|=n and G has no nondominating holes,then V(G)can be orded into a sequence v1v2…vn such that the neighbour set of vi in G[?v1,v2,…,vi? consists of two cliques,consequently the degree of vi in G[{v1,v2,…,vi?]is?2(?(G)-1)and ?(G)?2?(G)-1.In other words,(4-hole,A)-free odd signable graphs have a linear binding function,and from the asymptotic point of view,the linear function is the optimal binding function of ?-bounded graphs.