2025/09/17 by Ran Chen, Di Wu, Chen, Ran +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C75 #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.2509.14135
openalex publication_date 2025/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Goedgebeur and Schaudt [J. Graph Theory 87 (2018) 188-207] conjectured that all 4-vertex-critical (P7,C3)-free graphs belongs to the family \cal G, which consists of seven explicitly defined graphs. In this paper, we establish a structural decomposition for (P2∪ P4,C3)-free graphs and show that the conjecture holds for this class. Consequently, we determine the chromatic number of (P2∪ P4, C3)-free graphs. 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 bull is a graph consisting of a triangle with two disjoint pendant edges. Notice that the class of (P2∪ P4, C3)-free graphs is a subclass of (P2∪ P4, bull)-free graphs. In this paper, we prove that a (P2∪ P4, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph. This generalizes the main result of Deng and Chang [Graphs Combin. (2025) 41: 63].