On Graph Associations

DOI10.1137/050626545MaRDI QIDQ3440270zbMATH OpenOpenAlexFDO

Authors Landon Rabern

Publication date 22 May 2007

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

Full work available at URL https://arxiv.org/abs/math/0606632, https://semanticscholar.org/paper/82f5cf8df5a6ae429c0ad9b29063e3eb13327a1a

zbMATH Keywords

graph coloringReed's conjecture

Mathematics Subject Classification ID

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

Abstract: We outline some ongoing work related to a conjecture of Reed cite{reed97} on $omega$, $Delta$, and $chi$. We conjecture that the complement of a counterexample $G$ to Reed's conjecture has connectivity on the order of $log(|G|)$. We prove that this holds for a family (parameterized by $epsilon>0$) of relaxed bounds; the $epsilon=0$ limit of which is Reed's upper bound.

Recommendations

• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• On Reed's conjecture about , and
• scientific article; zbMATH DE number 1286500
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• On bounding the difference of the maximum degree and the clique number

Cited in

(1)

• Special issue in honour of Landon Rabern

This page was built for publication: On Graph Associations

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