On Chromatic Number of Graphs without Certain Induced Subgraphs

Abstract

Gyarfas conjectured that for a given forest \(F\), there exists an integer function \(f(F,w(G))\) such that \(\chi(G) \leq f(F,w(G))\) for any \(F\)-free graph \(G\), where \(\chi(G)\) and \(w(G)\) are respectively, the chromatic number and the clique number of G. Let G be a \(C_5\)-free graph and \(k\) be a positive integer. We show that if \(G\) is \((kP_1, + P_2)\)-free for \(k \geq 2\), then \(\chi(G) \leq 2w^{k-1} \sqrt{w}\); if \(G\) is \((kP_1, + P_3)\)-free for \(k \geq 1\), then \(\chi(G) \leq w^k \sqrt{w}\). A graph \(G\) is \(k\)-divisible if for each induced subgraph \(H\) of \(G\) with at least one edge, there is a partition of the vertex set of \(H\) into \(k\) sets \({V_1,… , V_k}\) such that no \(V_i\); contains a clique of size \(w(G)\). We show that a \((2P_1+P_2)\)-free and \(C_5\)-free graph is \(2\)-divisible.