Improvement on Brook theorem for (3 Times K1)-free Graphs

2017/02/27 by Medha Dhurandhar, Dhurandhar, Medha
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1702.08151

openalex publication_date 2017/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Problem of finding an optimal upper bound for the chromatic no. of a (3 Times K1)-free graph is still open and pretty hard. Here we prove that for a (3 Times K1)-free graph G with maximum degree greater than or equal to 8, χ is less than or equal to max (maximum degree-1, ω). We also prove that if G is (3 Times K1)-free, ω is equal to 4 and maximum degree is greater than or equal to 7, then χ is less than or equal to maximum degree-1. This implies that Borodin & Kostochka Conjecture is true for (3 Times K1)-free graphs as a corollary.

Related

• Validity of Borodin and Kostochka Conjecture for 4 Times K1-free Graphs
• Improvement on Brook theorem for 2K2-free Graphs
• Validity of Borodin and Kostochka Conjecture for classes of graphs without a single, forbidden subgraph on 5 vertices
• Tight Chromatic Upper Bound for 3 Times K1, 2 Times K1 + (K2 UNION K1)-free Graphs
• Tight Chromatic Upper Bound for 3K1, K1+C4-free Graphs