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

Access to Document

10.1016/j.ejc.2017.05.007

Fingerprint Dive into the research topics of 'DP-colorings of graphs with high chromatic number'. Together they form a unique fingerprint.

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 = "Funding Information: The authors are grateful to the anonymous referees for their valuable comments and suggestions. Research of first author is supported by the Illinois Distinguished Fellowship. Research of second author is supported in part by NSF grant DMS-1600592 and grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. Research of third author is supported in part by CNSF grant 11571319.",

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 Inc.",

}

TY - JOUR

T1 - DP-colorings of graphs with high chromatic number

AU - Bernshteyn, Anton

AU - Kostochka, Alexandr

AU - Zhu, Xuding

N1 - Funding Information: The authors are grateful to the anonymous referees for their valuable comments and suggestions. Research of first author is supported by the Illinois Distinguished Fellowship. Research of second author is supported in part by NSF grant DMS-1600592 and grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. Research of third author is supported in part by CNSF grant 11571319.

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

VL - 65

SP - 122

EP - 129

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -