DP-colorings of graphs with high chromatic number

Anton Bernshteyn; Alexandr Kostochka; Xuding Zhu

doi:10.1016/j.ejc.2017.05.007

DP-colorings of graphs with high chromatic number

Anton Bernshteyn, Alexandr Kostochka, Xuding Zhu

Mathematics

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

Abstract

DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle (2015). We prove that for every n-vertex graph G whose chromatic number χ(G) is “close” to n, the DP-chromatic number of G equals χ(G). “Close” here means χ(G)≥n−O(n), and we also show that this lower bound is best possible (up to the constant factor in front of n), in contrast to the case of list coloring.

Original language	English (US)
Pages (from-to)	122-129
Number of pages	8
Journal	European Journal of Combinatorics
Volume	65
DOIs	https://doi.org/10.1016/j.ejc.2017.05.007
State	Published - Oct 2017

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.1016/j.ejc.2017.05.007

Library availability

Discover UIUC Full Text

Cite this

@article{781d0956e86544ca82ed706694d69391,

title = "DP-colorings of graphs with high chromatic number",

abstract = "DP-coloring is a generalization of list coloring introduced recently by Dvo{\v r}{\'a}k and Postle (2015). We prove that for every n-vertex graph G whose chromatic number χ(G) is “close” to n, the DP-chromatic number of G equals χ(G). “Close” here means χ(G)≥n−O(n), and we also show that this lower bound is best possible (up to the constant factor in front of n), in contrast to the case of list coloring.",

author = "Anton Bernshteyn and Alexandr Kostochka and Xuding Zhu",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Ltd",

year = "2017",

month = oct,

doi = "10.1016/j.ejc.2017.05.007",

language = "English (US)",

volume = "65",

pages = "122--129",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - DP-colorings of graphs with high chromatic number

AU - Bernshteyn, Anton

AU - Kostochka, Alexandr

AU - Zhu, Xuding

PY - 2017/10

Y1 - 2017/10

N2 - DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle (2015). We prove that for every n-vertex graph G whose chromatic number χ(G) is “close” to n, the DP-chromatic number of G equals χ(G). “Close” here means χ(G)≥n−O(n), and we also show that this lower bound is best possible (up to the constant factor in front of n), in contrast to the case of list coloring.

AB - DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle (2015). We prove that for every n-vertex graph G whose chromatic number χ(G) is “close” to n, the DP-chromatic number of G equals χ(G). “Close” here means χ(G)≥n−O(n), and we also show that this lower bound is best possible (up to the constant factor in front of n), in contrast to the case of list coloring.

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

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

U2 - 10.1016/j.ejc.2017.05.007

DO - 10.1016/j.ejc.2017.05.007

M3 - Article

AN - SCOPUS:85020524497

SN - 0195-6698

VL - 65

SP - 122

EP - 129

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

DP-colorings of graphs with high chromatic number

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this