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

At least 1 year old · documented by

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 v∈V(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 K⊆V(G)K\subseteq V(G) such that

∑v∈Kf(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

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

one has

α(G)≥∑v∈V(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.

References

Primary source

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

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.