Connectivity bound for graphs exceeding Reed's bound

About 20 years old · traced to

Let GG be a graph, with chromatic number χ\chi, clique number ω\omega, maximum degree Δ\Delta, order nn, and let κ‾=κ(G‾)\overline{\kappa}=\kappa(\overline{G}) denote the connectivity of its complement. The connectivity bound conjecture. There exists a constant C>0C>0 such that

χ>⌈12(ω+Δ+1)⌉⇒κ‾≥Clog⁡(n).\chi>\left\lceil\frac{1}{2}(\omega+\Delta+1)\right\rceil\Rightarrow\overline{\kappa}\geq C\log(n).

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.

References

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

No solutions have been posted yet.