Decomposing a planar graph of girth 5 into an independent set and a forest

DOI10.1016/j.jctb.2008.11.002zbMath1184.05029OpenAlexW2085219314WikidataQ56926606 ScholiaQ56926606MaRDI QIDQ1026008

Carsten Thomassen, Ken-ichi Kawarabayashi

Publication date: 23 June 2009

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2008.11.002

zbMATH Keywords

independent setsforestsplanar graphs of girth 5

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Planar graphs without normally adjacent short cycles ⋮ A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable ⋮ A note on orientation and chromatic number of graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Decomposing a triangle-free planar graph into a forest and a subcubic forest ⋮ From the plane to higher surfaces ⋮ Sparse Graphs Are Near-Bipartite ⋮ (Circular) backbone colouring: forest backbones in planar graphs ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ Planar graphs without short even cycles are near-bipartite

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some counterexamples associated with the three-color problem
• On acyclic colorings of planar graphs
• Every planar graph is 5-choosable
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• A short list color proof of Grötzsch's theorem
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Three-coloring Klein bottle graphs of girth five
• Decomposing a planar graph into degenerate graphs
• On a conjecture of B. Grünbaum