Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

2017/12/25 by Kim, Seog-Jin, Yu, Xiaowei
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1712.08999

Abstract

DP-coloring (also known as correspondence coloring) of a simple graph is a generalization of list coloring. It is known that planar graphs without 4-cycles adjacent to triangles are 4-choosable, and planar graphs without 4-cycles are DP-4-colorable. In this paper, we show that planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, which is an extension of the two results above.

Related

• Planar graphs without 7-cycles and butterflies are DP-4-colorable
• Every planar graph without i-cycles adjacent simultaneously to\n j-cycles and k-cycles is DP-4-colorable when i,j,k = 3,4,5
• DP-4-colorability of two classes of planar graphs
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• A Sufficient condition for DP-4-colorability