2022/02/26 by Wei Dong, Dong, Wei, Baogang Xu +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2202.13177
arxiv created 2022/02/26 · openalex publication_date 2022/02/26 · arxiv updated 2022/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph. We say that G is 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). We use Pt and Ct to denote a path and a cycle on t vertices, respectively. For two disjoint graphs F1 and F2, we use F1∪ F2 to denote the graph with vertex set V(F1)∪ V(F2) and edge set E(F1)∪ E(F2), and use F1+F2 to denote the graph with vertex set V(F1)∪ V(F2) and edge set E(F1)∪ E(F2)∪ \xy | x∈ V(F1) and y∈ V(F2)\. In this paper, we prove that (i) (P5, C5, K2, 3)-free graphs are perfectly divisible, (ii) χ(G)≤ 2ω2(G)-ω(G)-3 if G is (P5, K2,3)-free with ω(G)≥ 2, (iii) χ(G)≤ 3\over 2(ω2(G)-ω(G)) if G is (P5, K1+2K2)-free, and (iv) χ(G)≤ 3ω(G)+11 if G is (P5, K1+(K1∪ K3))-free.