Problem of finding an optimal upper bound for the chromatic no. of even 3K1-free graphs is still open and pretty hard. Here we prove Borodin & Kostochka Conjecture for 4K1-free graphs G i.e. If maximum degree of a { 4 Times K1}-free graph is greater than or equal to 9, then the chromatic number of the graph is less than or equal to maximum of { \omega} and { \delta-1}.
Categories: math.CO