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 ...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.展开更多
基金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.
