Connectivity bound for graphs exceeding Reed's bound
Connectivity bound for graphs exceeding Reed's bound
Let be a graph, with chromatic number , clique number , maximum degree , order , and let denote the connectivity of its complement. The connectivity bound conjecture. There exists a constant such that
This is intended to express that a graph violating Reed's conjectural upper bound must have a highly connected complement; the supplied source gives no resolution status.
Sources & referencesView supporting material
Primary source
landon rabern, “New upper bounds on the chromatic number of a graph”, arXiv:math/0606632 (2006).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.