The forest-path partition conjecture for planar graphs without 4-cycles and 6-cycles
The forest-path partition conjecture for planar graphs without 4-cycles and 6-cycles
Let a planar graph be a graph that can be embedded in the plane, and let a graph be forest if it is acyclic. A graph is a linear forest if each of its connected components is a path; write for the class of forests whose maximum degree is at most , and for the class of all forests. An -partition is a partition of the vertex set into two parts inducing, respectively, a graph in and a graph in .
Forest-path partition conjecture. Every planar graph without -cycles and -cycles has an -partition.
This conjecture seeks to strengthen known vertex-partition results for planar graphs excluding 4-cycles and 6-cycles: such graphs are known to admit both a -partition and an -partition, while the conjectured partition replaces the two independent-set parts with a single forest and retains a bounded-degree forest part. The source presents this as an open problem.
Sources & referencesView supporting material
Primary source
Pongpat Sittitrai and Kittikorn Nakprasit, “Partitioning planar graphs without 4-cycles and 6-cycles into a forest and a disjoint union of paths”, arXiv:2203.06466 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.