Borodin–Kostochka’s Conjecture on \(\{P_2\cup P_3,C_4\}\)-Free Graphs

Let \(P_n\) $P_n$ and \(C_n\) $C_n$ denote the induced path and cycle on n vertices, respectively. For two graphs \(H_1\) $H_1$ and \(H_2\) $H_2$ , we use \(H_1\cup H_2\) $H_1\cup H_2$ to denote the graph with vertex set \(V(H_1)\cup V(H_2)\) $V(H_1)\cup V(H_2)$ and edge set \(E(H_1)\cup E(H_2)\) $E(H_1)\cup E(H_2)$ . Let \(\Delta (G)\) $\mathrm{\Delta }(G)$ , \(\chi (G)\) $\chi (G)$ and \(\omega (G)\) $\omega (G)$ denote the maximum degree, chromatic number and clique number of G, respectively. The Borodin–Kostochka Conjecture states that for a graph G, if \(\Delta (G)\ge 9\) $\mathrm{\Delta }(G)\ge 9$ , then \(\chi (G)\le \max \{\Delta (G)-1,\omega (G)\}\) $\chi (G)\le max\{\mathrm{\Delta }(G)-1,\omega (G)\}$ . In this paper, we prove the conjecture for \(\{P_2\cup P_3,C_4\}\) $\{P_2\cup P_3,C_4\}$ -free graphs.