Splitting a planar graph of girth 5 into two forests with trees of small diameter

DOI10.1016/j.disc.2018.04.007zbMath1387.05055OpenAlexW2800944282WikidataQ129969223 ScholiaQ129969223MaRDI QIDQ1752682

Alekseĭ Nikolaevich Glebov

Publication date: 24 May 2018

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

Full work available at URL: https://doi.org/10.1016/j.disc.2018.04.007

zbMATH Keywords

planar graphforestpath partitionlist colouring\(P_k\)-free colouring

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) Coloring of graphs and hypergraphs (05C15)

Related Items

Path partitioning planar graphs of girth 4 without adjacent short cycles ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Path partitioning planar graphs with restrictions on short cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Planar graphs with girth at least 5 are \((3, 5)\)-colorable
• Decomposing a planar graph of girth 5 into an independent set and a forest
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Every planar graph is 5-choosable
• A new proof of Grünbaum's 3 color theorem
• List improper colorings of planar graphs with prescribed girth
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• Path partitions of planar graphs
• Graphs with forbidden subgraphs
• List strong linear 2-arboricity of sparse graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
• Partition of a planar graph with girth 6 into two forests with chain length at most 4
• Improper choosability of graphs and maximum average degree