View PDF HTML (experimental)

Abstract: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. In this paper, we establish a structural theorem for connected $(P_2\cup P_4,C_3)$-free graphs. As a consequence, we prove that the Mycielski-Grötzsch graph is the unique $4$-vertex-critical graph in this class, thereby confirming the conjecture of Goedgebeur and Schaudt for $(P_2\cup P_4,C_3)$-free graphs. Our structural theorem also yields a characterization of the chromatic number of these graphs and an $O(n^4)$-time algorithm for deciding whether an $n$-vertex $(P_2\cup P_4,C_3)$-free graph is $3$-colorable.
We further study perfect divisibility in the larger class of $(P_2\cup P_4,\text{bull})$-free graphs. We prove that a $(P_2\cup P_4,\text{bull})$-free graph is perfectly divisible if and only if it is Mycielski-Grötzsch graph-free. This result generalizes the main theorem of Deng and Chang [Graphs Combin. 41 (2025), 63].

Submission history

From: Xiaowen Zhang [view email]
[v1] Wed, 17 Sep 2025 16:14:32 UTC (43 KB)
[v2] Mon, 23 Mar 2026 06:33:55 UTC (93 KB)
[v3] Wed, 9 Sep 2026 05:51:20 UTC (94 KB)