Validity of Borodin and Kostochka Conjecture for classes of graphs without a single, forbidden subgraph on 5 vertices

Abstract

Problem of finding an optimal upper bound for the chromatic no. of a graph is still open and very hard. Borodin and Kostochka Conjecture is still open and if proved will improve Brook bound on Chromatic no. of a graph. Here we prove Borodin & Kostochka Conjecture for (1) (P4 Union K1)-free (2) P5-free (3) Chair-free graphs and 4) graphs with dense neighbourhoods. Certain known results follow as Corollaries.

6 pages. arXiv admin note: text overlap with arXiv:1801.01310