Planar Graphs Without 4-Cycles Adjacent to Triangles are DP-4-Colorable

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...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2019-05, Vol.35 (3), p.707-718
Main Authors: Kim, Seog-Jin, Yu, Xiaowei
Format: Article
Language:English
Subjects:
Coloring
Combinatorics
Engineering Design
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 implies the two results above.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-019-02028-z