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 F1\mathcal{F}_1 for the class of forests whose maximum degree is at most 11, and F\mathcal{F} for the class of all forests. An (F1,F)(\mathcal{F}_1,\mathcal{F})-partition is a partition of the vertex set into two parts inducing, respectively, a graph in F1\mathcal{F}_1 and a graph in F\mathcal{F}.

Forest-path partition conjecture. Every planar graph without 44-cycles and 66-cycles has an (F1,F)(\mathcal{F}_1,\mathcal{F})-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 (Δ2,I,I)(\Delta_2,\mathcal{I},\mathcal{I})-partition and an (F1,I,I)(\mathcal{F}_1,\mathcal{I},\mathcal{I})-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

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.