The weighted Caro–Wei obstruction conjecture for odd-cycle blowups
Let be a graph, let be the degree of , let be its independence number, and let satisfy
for every . A blowup of an odd cycle is a graph obtained from a cycle of length by replacing its vertices with nonempty cliques, with adjacency between cliques corresponding to adjacency on the cycle.
Weighted Caro–Wei obstruction conjecture. Unless contains either a clique such that
or a subgraph isomorphic to a blowup of a cycle of length such that
one has
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 and ; 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
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.