Improvement on Brook theorem for 2K2-free Graphs

2017/02/03 by Dhurandhar, Medha
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1702.00914

Abstract

Here we prove that for a 2K2-free graph G with maximum degree greater than or equal to 5, the chromatic number is less than or equal to maxmaximum degree-1, maximum clique size. This implies that Borodin & Kostochka Conjecture is true for 2K2-free graphs.

Related

• Improvement on Brook theorem for (3 Times K1)-free Graphs
• Validity of Borodin & Kostochka Conjecture for a Class of Graphs
• Validity of Borodin and Kostochka Conjecture for 4 Times K1-free Graphs
• Validity of Borodin and Kostochka Conjecture for classes of graphs without a single, forbidden subgraph on 5 vertices
• A Brooks' Theorem for Triangle-Free Graphs