Large graphs with bounded independence number have swap sets

About 9 years old · traced to

Let GG be a graph, let α(G)\alpha(G) denote its independence number, and let a swap set mean the graph structure defined in the paper that supports the relevant disjoint dominating sets and matching. Bounded-independence swap-set conjecture. For every constant xx there is a positive constant yy such that, if

α(G)=xand∣V(G)∣≥y,\alpha(G)=x \quad\text{and}\quad |V(G)|\geq y,

then GG has a swap set.

The conjecture predicts that sufficiently large graphs with fixed independence number necessarily possess swap sets. The supplied text gives no resolution status.

References

Primary source

William F. Klostermeyer, Margaret-Ellen Messinger and Alejandro Angeli Ayello, “Disjoint Dominating Sets with a Perfect Matching”, arXiv:1708.09774 (2017).

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.