Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)

DOI10.1016/j.disc.2009.05.025zbMath1221.05147OpenAlexW1980600723WikidataQ122861675 ScholiaQ122861675MaRDI QIDQ968410

Anja Kohl, Ingo Schiermeyer

Publication date: 5 May 2010

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

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

zbMATH Keywords

chromatic numbercoloringReed's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Chromatic number of \(P_5\)-free graphs: Reed's conjecture, Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, Combinatorics. Abstracts from the workshop held January 1--7, 2023, A note on Reed's conjecture for triangle-free graphs, Large cliques in graphs with high chromatic number, Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors, Graph coloring approach with new upper bounds for the chromatic number: team building application, Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs, Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex-disjoint triangles in claw-free graphs with minimum degree at least three
• Bounding χ in terms of ω and Δ for quasi-line graphs
• A Note On Reed's Conjecture
• Small graphs with chromatic number 5: A computer search
• Handbook of Graph Theory
• A new upper bound for the chromatic number of a graph
• 25 pretty graph colouring problems