Kowalik et al.'s conjecture on induced forests in planar graphs of girth at least five

At least 11 years old · documented by

Let GG be a finite simple planar graph of order nn and girth at least 55, where the girth is the length of a shortest cycle.

Kowalik et al.'s conjecture. The graph GG admits an induced forest of order at least

7n10.\frac{7n}{10}.

This conjecture seeks a stronger induced-forest bound for planar graphs excluding short cycles. The source describes a companion result as a first step toward the conjecture, but does not state that the conjecture has been resolved.

References

Primary source

François Dross, Mickael Montassier and Alexandre Pinlou, “A lower bound on the order of the largest induced forest in planar graphs with high girth”, arXiv:1504.01949 (2015).

Additional references

2 papers in this index state this conjecture (2014–2015). The statement above is taken from the most recent of them; the others are arXiv:1409.1348.

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.