Conjecture on the induced forest number of Paley graphs of square order

About 3 years old · traced to

Let q>7q>7 be a prime power, and let P(q2)\mathcal{P}(q^2) denote the Paley graph on the finite field of order q2q^2. Let τ(G)\tau(G) denote the maximum order of an induced forest in a graph GG. Induced forest conjecture. For q>7q>7 a prime power,

τ(P(q2))=q+1.\tau(\mathcal{P}(q^2))=q+1.

The preceding computational searches found that adding two vertices to a maximum independent set does not produce a forest for all prime powers 7<q≤677<q\leq 67, suggesting that the smaller examples are anomalies. The conjecture predicts the exact maximum induced-forest order for Paley graphs of square order beyond these small cases.

References

Primary source

Karen Gunderson, Karen Meagher, Joy Morris and Venkata Raghu Tej Pantangi, “Induced forests in some distance-regular graphs”, arXiv:2301.05207 (2023).

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.