2025/04/21 by Baogang Xu, Xu, Baogang, Miaoxia Zhuang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2504.14863
openalex publication_date 2025/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A fork is a graph obtained from K1,3 (usually called claw) by subdividing an edge once. A graph is perfectly divisible if for each of its induced subgraph H, V(H) can be partitioned into A and B such that H[A] is perfect and ω(H[B]) < ω(H). In this paper, we prove that the perfect divisibility of fork-free graphs is equivalent to that of claw-free graphs. We also prove that, for F∈ \P7, P6∪ K1\, each (fork, F)-free graph G is perfectly divisible and hence χ(G)≤ \binomω(G)+12.