Ran Chen

activity

20232026

collaborators

11 papers

math.CO2026

Perfect divisibility and perfect-Pollyanna in bull-free graphs

Ran Chen, Paras Vinubhai Maniya, Di Wu +1

A graph $G$ is {\em perfectly divisible} if, for each induced subgraph $H$ of $G$ , $V (H)$ can be partitioned into $A$ and $B$ such that $H [A]$ is perfect and $ω (H [B]) < ω (H)$ . A {\em…

math.CO2025

On Perfect Divisibility of Bull-Free Graphs Without Long Paths

Ran Chen, Di Wu, Junran Yu +1

A graph $G$ is {\em perfectly divisible} if, for every induced subgraph $H$ of $G$ , $V (H)$ can be partitioned into $A$ and $B$ such that $H [A]$ is perfect and $ω (H [B]) < ω (H)$ . Chudn…

math.CO2025

Structure, Coloring, and Perfect Divisibility of $(P_{2} \cup P_{4}, C_{3})$ -Free Graphs

Di Wu, Xiaowen Zhang

Goedgebeur and Schaudt [J. Graph Theory 87 (2018), 188-207] conjectured that every $4$ -vertex-critical $(P_{7}, C_{3})$ -free graph belongs to a family of seven explicitly defined graphs…

math.CO2025

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…

math.CO2025

Perfect divisibility of (fork, antifork $\cup K_{1}$ )-free graphs

Ran Chen, Baogang Xu, Miaoxia Zhuang

A {\em fork} is a graph obtained from $K_{1, 3}$ (usually called {\em claw}) by subdividing an edge once, an {\em antifork} is the complement graph of a fork, and a {\em co-cricket}…

math.CO2025

Coloring of graphs without long odd holes

Ran Chen, Baogang Xu

A {\em hole} is an induced cycle of length at least 4, a $k$ -hole is a hole of length $k$ , and an {\em odd hole} is a hole of odd length. Let $ℓ \geq 2$ be an integer. Let ${\cal…

math.CO2024

Nearly optimal coloring of some C4-free graphs

Ran Chen, Baogang Xu

A class $G$ of graphs is $χ$ -{\em polydet} if $G$ has a polynomial binding function $f$ and there is a polynomial time algorithm to determine an $f (ω (G))$ -coloring of…

math.CO2024

Structure and linear-Pollyanna for some square-free graphs

Ran Chen, Baogang Xu

We use $P_{t}$ and $C_{t}$ to denote a path and a cycle on $t$ vertices, respectively. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges, a {\em hammer}…

math.CO2024

Coloring some $(P_{6}, C_{4})$ -free graphs with $Δ - 1$ colors

Ran Chen, Di Wu, Xiaowen Zhang

The Borodin-Kostochka Conjecture states that for a graph $G$ , if $Δ (G) \geq 9$ , then $χ (G) \leq max {Δ (G) - 1, ω (G)}$ . We use $P_{t}$ and $C_{t}$ to denote a path and a cycle on $t$ vertice…

math.CO2023

Structure and coloring of a family of ( $P_{7}, C_{5}$ )-free graphs

Ran Chen, Baogang Xu

Let $P_{t}$ and $C_{t}$ be a path and a cycle on $t$ vertices, respectively. In 2021, Choudum {\em et al.} [Disc. Math. 344 (2021) 112244] determined the structures of $(P_{7}, C_{7}, C_{4}$ ,…

math.CO2023

Structure and coloring of some ( $P_{7}, C_{4}$ )-free graphs

Ran Chen, Di Wu, Baogang Xu

Let $G$ be a graph. We use $P_{t}$ and $C_{t}$ to denote a path and a cycle on $t$ vertices, respectively. A {\em diamond} is a graph obtained from two triangles that share exactly one…

Perfect divisibility and perfect-Pollyanna in bull-free graphs

On Perfect Divisibility of Bull-Free Graphs Without Long Paths

Structure, Coloring, and Perfect Divisibility of (P2​∪P4​,C3​)-Free Graphs

The optimal binding function for (cap, even hole)-free graphs

Perfect divisibility of (fork, antifork∪K1​)-free graphs

Coloring of graphs without long odd holes

Nearly optimal coloring of some C4-free graphs

Structure and linear-Pollyanna for some square-free graphs

Coloring some (P6​,C4​)-free graphs with Δ−1 colors

Structure and coloring of a family of (P7​,C5​)-free graphs

Structure and coloring of some (P7​,C4​)-free graphs

Structure, Coloring, and Perfect Divisibility of $(P_{2} \cup P_{4}, C_{3})$ -Free Graphs

Perfect divisibility of (fork, antifork $\cup K_{1}$ )-free graphs

Coloring some $(P_{6}, C_{4})$ -free graphs with $Δ - 1$ colors

Structure and coloring of a family of ( $P_{7}, C_{5}$ )-free graphs

Structure and coloring of some ( $P_{7}, C_{4}$ )-free graphs