On the Chromatic Number of a Family of odd Hole Free Graphs
A hole is an induced cycle of length at least 4,a hole of odd length(resp.even length)is called an odd hole(resp.even hole).An HVN is a graph composed by a vertex adjacent to both ends of an edge in K4.Let H be the complement of a cycle on 7 vertices.Chudnovsky et al.in[J.Combin.Theory B,2010,100:313-331]proved that every(odd hole,K4)-free graph is 4-colorable and is 3-colorable if it does not contain H as an induced subgraph.In this paper,we use the idea and proving technique of Chudnovsky et al.to generalize this conclusion to(odd hole,HVN)-free graphs.Let G be an(odd hole,HVN)-free graph.We prove that if G contains H as an induced subgraph,then it either has a special cutset or is in two classes of pre-defined graphs.As its corollary,we show that x(G)≤ω(G)+1,and the equality holds if and only if ω(G)=3 and G has H as an induced subgraph.