Submit progress

on Upper bound on the independence number of a connected graph

The statement

Let $G$ be a finite simple connected graph on at least two vertices such that its complement $\overline{G}$ is also connected. For each vertex $v$ of $G$ , let $l(v)$ denote the independence number of the subgraph induced by the neighborhood of $v$ in $G$ . Let $\lambda = \max_{v \in V(G)} l(v)$ . Let $\mathrm{diam}(\overline{G})$ denote the diameter of the complement graph $\overline{G}$ , i.e., the maximum over all pairs of vertices of the length of a shortest path between them in $\overline{G}$ . Prove that the independence number $\alpha(G)$ satisfies

\alpha(G) \leq \left\lceil \frac{\lambda + \frac{1}{2} \cdot \mathrm{diam}(\overline{G})}{2} \right\rceil.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.