Edge DP-coloring in planar graphs

Li Zhang; You Lu; Shenggui Zhang

doi:10.1016/j.disc.2021.112314

Edge DP-coloring in planar graphs

Li Zhang, You Lu, Shenggui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

As a generalization of list coloring, DP-coloring of graphs was introduced by Dvořák and Postle (2018). Recently, Bernshteyn and Kostochka introduced edge DP-coloring of graphs which is naturally corresponding to the DP-coloring of their line graphs. Let χ_DP^′(G) denote the edge DP-chromatic number of a graph G. In this paper, we prove that if G is a planar graph with maximum degree Δ and without cycles of length k, then (1) χ_DP^′(G)=Δ if either Δ≥7 and k=4 or Δ≥8 and k=3; (2) χ_DP^′(G)≤Δ+1 if Δ≥9.

Original language	English
Article number	112314
Journal	Discrete Mathematics
Volume	344
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2021.112314
State	Published - May 2021

Keywords

Edge DP-coloring
Edge coloring
Edge list coloring
Planar graph

Access to Document

10.1016/j.disc.2021.112314

Cite this

@article{b9bb50868c6840b68a258e93f163fc3c,

title = "Edge DP-coloring in planar graphs",

abstract = "As a generalization of list coloring, DP-coloring of graphs was introduced by Dvo{\v r}{\'a}k and Postle (2018). Recently, Bernshteyn and Kostochka introduced edge DP-coloring of graphs which is naturally corresponding to the DP-coloring of their line graphs. Let χDP′(G) denote the edge DP-chromatic number of a graph G. In this paper, we prove that if G is a planar graph with maximum degree Δ and without cycles of length k, then (1) χDP′(G)=Δ if either Δ≥7 and k=4 or Δ≥8 and k=3; (2) χDP′(G)≤Δ+1 if Δ≥9.",

keywords = "Edge DP-coloring, Edge coloring, Edge list coloring, Planar graph",

author = "Li Zhang and You Lu and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = may,

doi = "10.1016/j.disc.2021.112314",

language = "英语",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Edge DP-coloring in planar graphs

AU - Zhang, Li

AU - Lu, You

AU - Zhang, Shenggui

PY - 2021/5

Y1 - 2021/5

N2 - As a generalization of list coloring, DP-coloring of graphs was introduced by Dvořák and Postle (2018). Recently, Bernshteyn and Kostochka introduced edge DP-coloring of graphs which is naturally corresponding to the DP-coloring of their line graphs. Let χDP′(G) denote the edge DP-chromatic number of a graph G. In this paper, we prove that if G is a planar graph with maximum degree Δ and without cycles of length k, then (1) χDP′(G)=Δ if either Δ≥7 and k=4 or Δ≥8 and k=3; (2) χDP′(G)≤Δ+1 if Δ≥9.

AB - As a generalization of list coloring, DP-coloring of graphs was introduced by Dvořák and Postle (2018). Recently, Bernshteyn and Kostochka introduced edge DP-coloring of graphs which is naturally corresponding to the DP-coloring of their line graphs. Let χDP′(G) denote the edge DP-chromatic number of a graph G. In this paper, we prove that if G is a planar graph with maximum degree Δ and without cycles of length k, then (1) χDP′(G)=Δ if either Δ≥7 and k=4 or Δ≥8 and k=3; (2) χDP′(G)≤Δ+1 if Δ≥9.

KW - Edge DP-coloring

KW - Edge coloring

KW - Edge list coloring

KW - Planar graph

UR - http://www.scopus.com/inward/record.url?scp=85100061777&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112314

DO - 10.1016/j.disc.2021.112314

M3 - 文章

AN - SCOPUS:85100061777

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 112314

ER -

Edge DP-coloring in planar graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this