A Note On Reed's Conjecture

DOI10.1137/060659193MaRDI QIDQ3629477zbMATH OpenOpenAlexWikidataFDO

Authors Landon Rabern

Publication date 27 May 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604499

zbMATH Keywords

chromatic numbergraph coloringReed's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: In cite{reed97}, Reed conjectures that the inequality $chi(G)leqleftlceilextstyle1/2(omega(G)+Delta(G)+1)ightceil$ holds for any graph $G$. We prove this holds for a graph $G$ if $$ is disconnected. From this it follows that the conjecture holds for graphs with $chi(G)>leftlceilfrac|G|2ightceil$. In addition, the conjecture holds for graphs with $Delta(G)geq|G|-sqrt|G|+2alpha(G)+1$. In particular, Reed's conjecture holds for graphs with $Delta(G)geq|G|-sqrt|G|+7$. Using these results, we proceed to show that if $|G|$ is an even order counterexample to Reed's conjecture, then $$ has a 1-factor. Hence, for any even order graph $G$, if $chi(G)>extstyle1/2(omega(G)+Delta(G)+1)+1$, then $$ is matching covered.

Recommendations

• On Reed's conjecture about \(\omega\), \(\Delta\) and \(\chi\)
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• A note on Reed's conjecture for triangle-free graphs
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture

Cited in

(19)

• scientific article; zbMATH DE number 3849971 (Why is no real title available?)
• Graph coloring approach with new upper bounds for the chromatic number: team building application
• A contribution to Reich's conjecture
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• Large cliques in graphs with high chromatic number
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• On Reed's conjecture about \(\omega\), \(\Delta\) and \(\chi\)
• Randomly colouring graphs (a combinatorial view)
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• The chromatic discrepancy of graphs
• A note on Reed's conjecture for triangle-free graphs
• On hitting all maximum cliques with an independent set
• Special issue in honour of Landon Rabern
• A superlocal version of Reed's conjecture
• scientific article; zbMATH DE number 4156623 (Why is no real title available?)
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• Square-Free Graphs with No Six-Vertex Induced Path
• Combinatorics. Abstracts from the workshop held January 1--7, 2023

This page was built for publication: A Note On Reed's Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3629477)