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

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

Sources & referencesView supporting material

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.