Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests

DOI10.1016/j.disc.2020.112172zbMath1455.05059arXiv2003.09929OpenAlexW3092288236MaRDI QIDQ2219964

Boram Park, Ilkyoo Choi, Eun-Kyung Cho

Publication date: 21 January 2021

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

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

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)

Related Items (6)

Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition ⋮ A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles ⋮ Independent domination of graphs with bounded maximum degree ⋮ Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Steinberg's conjecture is false
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• A note on the three color problem
• Colorings of plane graphs: a survey
• Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
• Near-colorings: non-colorable graphs and NP-completeness
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Defective 2-colorings of sparse graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• On the linear vertex-arboricity of a planar graph
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• Improper coloring of graphs on surfaces
• Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

This page was built for publication: Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests