Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition

DOI10.1016/J.DAM.2023.10.002MaRDI QIDQ6143874zbMATH OpenOpenAlexFDO

Authors Wipawee Tangjai, Kittikorn Nakprasit, Keaitsuda Nakprasit, Pongpat Sittitrai

Publication date 24 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.10.002

zbMATH Keywords

cycledischarging methodforestplanar graphvertex partition

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Partitioning planar graphs into bounded degree forests
• A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable
• Path partitioning planar graphs of girth 4 without adjacent short cycles

Cites work

• An (F1,F4)‐partition of graphs with low genus and girth at least 6
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• Defective 2-colorings of sparse graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• scientific article; zbMATH DE number 3565019 (Why is no real title available?)
• scientific article; zbMATH DE number 1882351 (Why is no real title available?)
• Improper choosability of graphs and maximum average degree
• Near-colorings: non-colorable graphs and NP-completeness
• On the linear vertex-arboricity of a planar graph
• On the vertex partition of planar graphs into forests with bounded degree
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
• Planar graphs without short even cycles are near-bipartite
• The 3-colorability of planar graphs without cycles of length 4, 6 and 9
• The Point-Arboricity of Planar Graphs
• Threshold for path colorings of planar graphs

Cited in

(3)

• Partitioning planar graphs into bounded degree forests
• \((\mathcal{F}_1, \mathcal{F})\)-partition of plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles
• On \((\mathscr{F, F}_2)\)-partitionability of planar graphs without \(\{4,7\}\)-cycles

This page was built for publication: Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6143874)