Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs

DOI10.1016/j.disc.2011.02.021zbMath1216.05026MaRDI QIDQ536214

T. Karthick, N. R. Aravind, C. R. Subramanian

Publication date: 16 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.02.021

zbMATH Keywords

chromatic number; clique number; vertex coloring; maximum degree

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

A Note on Hitting Maximum and Maximal Cliques With a Stable Set, Chromatic number of \(P_5\)-free graphs: Reed's conjecture, Star chromatic bounds, A superlocal version of Reed's conjecture, On bounding the difference of the maximum degree and the clique number, A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• Stability number of bull- and chair-free graphs revisited
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Vertex colouring and forbidden subgraphs -- a survey
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• An upper bound for the chromatic number of line graphs
• On a property of the class of n-colorable graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• A Note On Reed's Conjecture
• Graph Classes: A Survey
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• The smallest triangle-free 4-chromatic 4-regular graph
• 25 pretty graph colouring problems