2-divisibility of Some Odd Hole Free Graphs  

作　　者：Wei DONG Jia-lei SONG Bao-gang XU 

机构地区：[1]School of Information and Engineering,Nanjing Xiaozhuang University,Nanjing 211171,China [2]Institute of Mathematics,School of Mathematical Sciences,Nanjing Normal University,Nanjing 210023,China

出　　处：《Acta Mathematicae Applicatae Sinica》2022年第3期710-718,共9页应用数学学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.11931006)。

摘　　要：Let G be a graph.We say that G is 2-divisible if for each induced subgraph H of G,either V(H)is a stable set,or V(H)can be partitioned into two sets A and B such thatω(H[A])<ω(H)andω(H[B])<ω(H).A hole is an induced cycle of length at least 4,a bull is a graph consisting of a triangle with two disjoint pendant edges,a diamond is the graph obtained from K4 by removing an edge,a dart denotes the graph obtained from a diamond by adding a pendant edge to one vertex of degree 3,and a racket denotes the graph obtained from a diamond by adding a pendant edge to one vertex of degree 2.In this paper,we prove that every{odd hole,H}-free graph is 2-divisible,where H is a dart,or a racket,or a bull.As corollaries,X(G)≤min{2ω^(G)-1,(ω^(G)/2+1)}if G is{odd hole,dart}-free,or{odd hole,racket}-free,or{odd hole,bull}-free.

关 键 词：HOLE odd hole 2-divisibility 

分 类 号：O157.5[理学—数学]