Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable

2024/12/26 by Ligang Jin, Jin, Ligang, Yingli Kang +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2412.19059

Abstract

The concept of DP-coloring of graphs was introduced by Dvořák and Postle, and was used to prove that planar graphs without cycles of length from 4 to 8 are 3-choosable. In the same paper, they proposed a more natural and stronger claim that such graphs are DP-3-colorable. This paper confirms that claim by proving a stronger result that planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable.

Cited by

• The square of every subcubic planar graph without 4-cycles and 5-cycles is 7-choosable

Related

• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Planar graphs without cycles of length 4 or 5 are (7m:2m)-DP-colorable
• DP-3-coloring of some planar graphs