Large graphs with bounded independence number have swap sets

From papers

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)=xandV(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.

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

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

Solutions 0

No solutions have been posted yet.