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!
|
| _version_ | 1832588098425323520 |
|---|---|
| author | Fan Yang Xiangwen Li Ziwen Huang |
| author_facet | Fan Yang Xiangwen Li Ziwen Huang |
| author_sort | Fan Yang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e9a7db265f5e4df29b82f25ee640905a |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-e9a7db265f5e4df29b82f25ee640905a2025-01-24T13:39:41ZengMDPI AGMathematics2227-73902025-01-0113219010.3390/math13020190DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-CyclesFan Yang0Xiangwen Li1Ziwen Huang2School of Mathematics and Science, Nanjing Tech University, Nanjing 211816, ChinaSchool of Mathematics & Statistics, Central China Normal University, Wuhan 430079, ChinaSchool of Mathematics and Computer Science & Center of Applied Mathematics, Yichun University, Yichun 336000, ChinaIn 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.https://www.mdpi.com/2227-7390/13/2/190planar graphDP-4-colorablelist coloring |
| spellingShingle | Fan Yang Xiangwen Li Ziwen Huang DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles Mathematics planar graph DP-4-colorable list coloring |
| title | DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles |
| title_full | DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles |
| title_fullStr | DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles |
| title_full_unstemmed | DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles |
| title_short | DP-4-Colorability on Planar Graphs Excluding 7-Cycles Adjacent to 4- or 5-Cycles |
| title_sort | dp 4 colorability on planar graphs excluding 7 cycles adjacent to 4 or 5 cycles |
| topic | planar graph DP-4-colorable list coloring |
| url | https://www.mdpi.com/2227-7390/13/2/190 |
| work_keys_str_mv | AT fanyang dp4colorabilityonplanargraphsexcluding7cyclesadjacentto4or5cycles AT xiangwenli dp4colorabilityonplanargraphsexcluding7cyclesadjacentto4or5cycles AT ziwenhuang dp4colorabilityonplanargraphsexcluding7cyclesadjacentto4or5cycles |