Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

DOI10.1016/j.endm.2015.06.037zbMath1346.05228arXiv1601.01523OpenAlexW2964100745MaRDI QIDQ5890907

Alexandre Pinlou, Mickaël Montassier, Franois Dross, François Dross

Publication date: 14 October 2016

Published in: Electronic Notes in Discrete Mathematics, European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.01523

zbMATH Keywords

forestvertex partitionbounded degreetriangle-free planar graph\((\mathcal{F},\mathcal{F}_5)\)-partition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (16)

A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition ⋮ Partitioning \(P_4\)-tidy graphs into a stable set and a forest ⋮ A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles ⋮ Decomposing a triangle-free planar graph into a forest and a subcubic forest ⋮ Unnamed Item ⋮ Sparse Graphs Are Near-Bipartite ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ Minimum size of feedback vertex sets of planar graphs of girth at least five ⋮ On the vertex partition of planar graphs into forests with bounded degree ⋮ Planar graphs without short even cycles are near-bipartite ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5 ⋮ Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest

Cites Work

• Unnamed Item
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Decomposing a planar graph into degenerate graphs
• Near-colorings: non-colorable graphs and NP-completeness
• On the vertex-arboricity of planar graphs
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• On the linear vertex-arboricity of a planar graph
• The Point-Arboricity of Planar Graphs

This page was built for publication: Partitioning a triangle-free planar graph into a forest and a forest of bounded degree