DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/2/190 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <i>G</i> that excludes 7-cycles adjacent to <i>k</i>-cycles (for each <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>=</mo><mn>4</mn><mo>,</mo><mn>5</mn></mrow></semantics></math></inline-formula>), 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. |
|---|---|
| ISSN: | 2227-7390 |