TxGraffiti's independence–matching conjecture for regular graphs

From papers

Let GG be a connected rr-regular graph with r>0r>0. Let α(G)\alpha(G) denote the independence number of GG, and let μ(G)\mu(G) denote its matching number. TxGraffiti's independence–matching conjecture. Then

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

and this bound is sharp. This is a generalized form of the example conjecture produced by the filtering heuristic, illustrating how a more general graph hypothesis can be retained for the same sharp inequality.

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.