The weighted Caro–Wei obstruction conjecture for odd-cycle blowups
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.
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
Sign in to submit a solution.
No solutions have been posted yet.