TxGraffiti's independence–matching conjecture for regular graphs

At least 1 year old · documented by

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.

References

Primary source

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

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.