← All problems

Large graphs with bounded independence number have swap sets

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
  1. 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.