×

zbMATH — the first resource for mathematics

On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph. (Russian) Zbl 1012.05133
It is proved that the vertex set of any planar graph with girth at least 5 can be partitioned into two subsets, \(V_1\) and \(V_2\), such that \(V_1\) is an independent set and the graph induced by \(V_2\) is acyclic. This settles a conjecture by Pyatkin and Stibitz.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite