Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

DOI10.1002/jgt.22093zbMath1367.05044arXiv1507.02815OpenAlexW2963703194MaRDI QIDQ4978291

Torsten Ueckerdt, Pascal Weiner, Maria A. Axenovich

Publication date: 8 August 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

2-coloringplanar graph decompositiondefective coloringpath forestsfragmented coloring

Mathematics Subject Classification ID

Paths and cycles (05C38) 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) Distance in graphs (05C12)

Related Items

Path partitioning planar graphs of girth 4 without adjacent short cycles, Path choosability of planar graphs, Facial incidence colorings of embedded multigraphs, Colorings of plane graphs without long monochromatic facial paths, Colouring planar graphs with bounded monochromatic components, Partitioning sparse graphs into an independent set and a graph with bounded size components, On the computational complexity of the bipartizing matching problem, Path partition of planar graphs with girth at least six, Unnamed Item, Path partitioning planar graphs with restrictions on short cycles, Splitting a planar graph of girth 5 into two forests with trees of small diameter, WORM colorings of planar graphs, Islands in Graphs on Surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• Relaxed two-coloring of cubic graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Near-colorings: non-colorable graphs and NP-completeness
• Defective choosability of graphs without small minors
• Graphs with forbidden subgraphs
• List strong linear 2-arboricity of sparse graphs
• On the linear vertex-arboricity of a planar graph
• Graph coloring with no large monochromatic components
• Deciding Relaxed Two-Colourability: A Hardness Jump
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• A 4-Color Theorem for Surfaces of Genus g
• Path chromatic numbers of graphs
• List Improper Colourings of Planar Graphs
• 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
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components
• Islands in Graphs on Surfaces
• Acyclic colorings of planar graphs