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

2021/01/05 by Medha Dhurandhar, Dhurandhar, Medha
Computer Science · Mathematics · #05C #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2101.01354

openalex publication_date 2021/01/05 · openalex created_date 2021/01/18 · openalex updated_date 2026/07/28

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.

Related

• Validity of Borodin and Kostochka Conjecture for 4 Times K1-free Graphs
• Validity of Borodin & Kostochka Conjecture for a Class of Graphs
• Borodin-Kostochka conjecture for a family of P₆-free graphs
• Coloring some (P₆,C₄)-free graphs with Δ-1 colors
• Improvement on Brook theorem for 2K2-free Graphs