6 papers
On minimal nonperfectly divisible fork-free graphs
Baogang Xu, Miaoxia Zhuang
A fork is a graph obtained from (usually called claw) by subdividing an edge once. A graph is perfectly divisible if for each of its induced subgraph , can be p…
Structure and linear-Pollyanna for some square-free graphs
Ran Chen, Baogang Xu
We use and to denote a path and a cycle on vertices, respectively. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges, a {\em hammer}…
The optimal binding function for (cap, even hole)-free graphs
Ran Chen, Baogang Xu, Yian Xu
A {\em hole} is an induced cycle of length at least 4, an {\em even hole} is a hole of even length, and a {\em cap} is a graph obtained from a hole by adding an additional vertex w…
Perfect divisibility of (fork, antifork)-free graphs
Ran Chen, Baogang Xu, Miaoxia Zhuang
A {\em fork} is a graph obtained from (usually called {\em claw}) by subdividing an edge once, an {\em antifork} is the complement graph of a fork, and a {\em co-cricket}…
Coloring of graphs without long odd holes
Ran Chen, Baogang Xu
A {\em hole} is an induced cycle of length at least 4, a -hole is a hole of length , and an {\em odd hole} is a hole of odd length. Let be an integer. Let ${\cal…
Nearly optimal coloring of some C4-free graphs
Ran Chen, Baogang Xu
A class of graphs is -{\em polydet} if has a polynomial binding function and there is a polynomial time algorithm to determine an -coloring…