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

DOI10.1016/j.disc.2011.02.021zbMath1216.05026OpenAlexW1775534754MaRDI 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 numberclique numbervertex coloringmaximum degree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Chromatic number of \(P_5\)-free graphs: Reed's conjecture ⋮ Star chromatic bounds ⋮ A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ A Note on Hitting Maximum and Maximal Cliques With a Stable Set ⋮ Star coloring of certain graph classes ⋮ Graph coloring approach with new upper bounds for the chromatic number: team building application ⋮ A superlocal version of Reed's conjecture ⋮ On bounding the difference of the maximum degree and the clique number ⋮ On indicated coloring of some classes of graphs

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

This page was built for publication: Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs