DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles

Abstract

In order to resolve Borodin’s Conjecture, DP-coloring was introduced in 2017 to extend the concept of list coloring. In previous works, it is proved that every planar graph without 7-cycles and butterflies is DP-4-colorable. And any planar graph that does not have 5-cycle adjacent to 6-cycle is DP-4-colorable. The existing research mainly focus on the forbidden adjacent cycles that guarantee the DP-4-colorability for planar graph. In this paper, we demonstrate that any planar graph G that excludes 7-cycles adjacent to k-cycles (for each k=4,5), and does not feature a Near-bow-tie as an induced subgraph, is DP-4-colorable. This result extends the findings of the previous works mentioned above.

Keywords

• planar graph
• DP-4-colorable
• list coloring