Connectivity bound for graphs exceeding Reed's bound

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.

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

No solutions have been posted yet.