Planar graphs without 5^--cycles at distance less than 3 are (I, F)-colorable

2023/11/06 by Zhen He, Tao Wang, He, Zhen +3
Computer Science · #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2311.02969

Abstract

A graph is (I, F)-colorable if its vertex set can be partitioned into two subsets, one of which is an independent set, and the other induces a forest. In this paper, we prove that every planar graph without 5^--cycles at distance less than 3 is (I, F)-colorable.

Related

• Planar graphs without cycles of length 4 or 5 are (11:3)-colorable
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9
• A comment to: On 3-colorable planar graphs without short cycles
• Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable