Planar graphs without cycles of length from 4 to 7 are near-bipartite

2022/04/10 by Lili Hao, Weihua Yang, Hao, Lili +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2204.09639

openalex publication_date 2022/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph is near-bipartite if its vertex set can be partitioned into an independent set and a set which induces a forest. In this paper, planar graphs without cycles of length from 4 to 7 are shown to be near-bipartite.

Related

• Partitioning planar graphs without 4-cycles and 6-cycles into a forest and a disjoint union of paths
• Planar graphs without 5^--cycles at distance less than 3 are (I, F)-colorable
• (I,F)-partition of planar graphs without cycles of length 4, 6, or 9
• Partitioning a Planar Graph into two Triangle-Forests
• Beyond-Planarity: Density Results for Bipartite Graphs