Caro–Davila–Pepper independence–matching conjecture for cubic graphs

From papers

Let GG be a connected cubic, equivalently 3-regular, graph. Let α(G)\alpha(G) denote the independence number of GG, and let μ(G)\mu(G) denote its matching number. Caro–Davila–Pepper independence–matching conjecture. Then

α(G)μ(G).\alpha(G)\leq\mu(G).

The conjecture is presented as an example of a TxGraffiti-generated relation between graph invariants. It was subsequently generalized and proved, so the original cubic-graph conjecture is solved.

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

Randy Davila, “Artificial intelligence and machine learning generated conjectures with TxGraffiti”, arXiv:2407.02731 (2024).

Solutions 0

No solutions have been posted yet.