The weighted Caro–Wei obstruction conjecture for odd-cycle blowups

From papers

Let GG be a graph, let d(v)d(v) be the degree of vv, let α(G)\alpha(G) be its independence number, and let f:V(G)Rf:V(G)\to\mathbb R satisfy

f(v)1d(v)f(v)\leq \frac{1}{d(v)}

for every vV(G)v\in V(G). A blowup of an odd cycle is a graph obtained from a cycle of length 2k+12k+1 by replacing its vertices with nonempty cliques, with adjacency between cliques corresponding to adjacency on the cycle.

Weighted Caro–Wei obstruction conjecture. Unless GG contains either a clique KV(G)K\subseteq V(G) such that

vKf(v)>1,\sum_{v\in K}f(v)>1,

or a subgraph HH isomorphic to a blowup of a cycle of length 2k+12k+1 such that

vV(H)f(v)>k,\sum_{v\in V(H)}f(v)>k,

one has

α(G)vV(G)f(v).\alpha(G)\geq\sum_{v\in V(G)}f(v).

This conjecture proposes that clique obstructions and blowups of odd cycles are essentially the only obstructions to the weighted independence-number bound. It is motivated by the examples discussed immediately before the conjecture, including blowups of C5C_5 and C7C_7; no resolution is supplied in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Tom Kelly and Luke Postle, “Improving the Caro-Wei bound and applications to Turán stability”, arXiv:2407.17363 (2024).

Solutions 0

No solutions have been posted yet.