Planar graphs without short even cycles are near-bipartite

DOI10.1016/j.dam.2020.04.017zbMath1443.05047arXiv2106.00159OpenAlexW3017886897MaRDI QIDQ777449

Runrun Liu, Gexin Yu

Publication date: 7 July 2020

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

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

zbMATH Keywords

planar graphs3-colorablenear-bipartite

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 (4)

Planar graphs without normally adjacent short cycles ⋮ A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The 3-colorability of planar graphs without cycles of length 4, 6 and 9
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Decomposing a planar graph of girth 5 into an independent set and a forest
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Decomposing a planar graph into degenerate graphs
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

This page was built for publication: Planar graphs without short even cycles are near-bipartite