Tight Chromatic Upper Bound for 3K1, K1+C4-free Graphs

2014/07/16 by Medha Dhurandhar, Dhurandhar, Medha
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1407.4199

2 pages

openalex publication_date 2014/07/16 · arxiv created 2015/05/15 · arxiv updated 2015/05/18 · 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 3K1-free graphs is still open and pretty hard. It was proved by Choudum et al that an upper bound on the chromatic no. of 3K1, K1+C4-free graphs, is 2ω. We improve this by proving that if G is 3K1, K1+C4-free, then its chromatic no. is less than or equal to 3ω divided by 2, where ω is the size of a maximum clique in G. Also we give examples to show that this bound is tight.

Related

• Tight Chromatic Upper Bound for 3K1, C5-free Graphs
• Tight Chromatic Upper Bound for 3 Times K1, 2 Times K1 + (K2 UNION K1)-free Graphs
• On the Tight Chromatic Bounds for a Class of Graphs without Three Induced Subgraphs
• Improvement on Brook theorem for (3 Times K1)-free Graphs
• Validity of Borodin and Kostochka Conjecture for 4 Times K1-free Graphs