Geodesic
On differences between DP-coloring and list coloring
Matematičeskie trudy, Tome 21 (2018) no. 2, pp. 61-71.

Voir la notice de l'article provenant de la source Math-Net.Ru

DP-Coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle [12]. Many known upper bounds for the list-chromatic number extend to the DP-chromatic number, but not all of them do. In this note we describe some properties of DP-coloring that set it aside from list coloring. In particular, we give an example of a planar bipartite graph with DP-chromatic number $4$ and prove that the edge-DP-chromatic number of a $d$-regular graph with $d\geq2$ is always at least $d+1$. 
@article{MT_2018_21_2_a1,
     author = {A. Yu. Bernshteyn and A. V. Kostochka},
     title = {On differences between {DP-coloring} and list coloring},
     journal = {Matemati\v{c}eskie trudy},
     pages = {61--71},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2018_21_2_a1/}
}
TY  - JOUR
AU  - A. Yu. Bernshteyn
AU  - A. V. Kostochka
TI  - On differences between DP-coloring and list coloring
JO  - Matematičeskie trudy
PY  - 2018
SP  - 61
EP  - 71
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2018_21_2_a1/
LA  - ru
ID  - MT_2018_21_2_a1
ER  - 
%0 Journal Article
%A A. Yu. Bernshteyn
%A A. V. Kostochka
%T On differences between DP-coloring and list coloring
%J Matematičeskie trudy
%D 2018
%P 61-71
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2018_21_2_a1/
%G ru
%F MT_2018_21_2_a1
A. Yu. Bernshteyn; A. V. Kostochka. On differences between DP-coloring and list coloring. Matematičeskie trudy, Tome 21 (2018) no. 2, pp. 61-71. http://geodesic.mathdoc.fr/item/MT_2018_21_2_a1/

[1] Bernshtein A., Kostochka A., Pron S., “O DP-raskraske grafov i multigrafov”, Sib. matem. zhurn., 58:1 (2017), 36–47 | MR

[2] Vizing V. G., “Ob otsenke khromaticheskogo klassa $p$-grafa”, Diskretnyi analiz, 1964, no. 3, 25–30

[3] Vizing V. G., “Raskraska vershin grafa v predpisannye tsveta”, Diskretnyi analiz, 1976, no. 29, 3–10 | Zbl

[4] Alon N., “Degrees and choice numbers”, Random Struct. Algorithms, 16:4 (2000), 364–368 | 3.0.CO;2-0 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] Alon N., Tarsi M., “Colorings and orientations of graphs”, Combinatorica, 12:2 (1992), 125–134 | DOI | MR | Zbl

[6] Bernshteyn A., “The asymptotic behavior of the correspondence chromatic number”, Discrete Math., 339:11 (2016), 2680–2692 | DOI | MR | Zbl

[7] Bernshteyn A., The Johansson–Molloy Theorem for DP-Coloring, 2017, arXiv: 1708.03843

[8] Bernshteyn A., Kostochka A., Sharp Dirac's Theorem for DP-Critical Graphs, 2016, arXiv: 1609.09122 | MR

[9] Borodin O., “Colorings of plane graphs: a survey”, Discrete Math., 313:4 (2013), 517–539 | DOI | MR | Zbl

[10] Borodin O. V., Kostochka A., Woodall D. R., “List edge and list total colorings of multigraphs”, J. Combin. Theory, Ser. B, 71:2 (1997), 184–204 | DOI | MR | Zbl

[11] Borodin O. V., Kostochka A., Woodall D. R., “On kernel-perfect orientations of line graphs”, Discrete Math., 191 (1998), 45–49 | DOI | MR | Zbl

[12] Dirac G. A., “A theorem of R. L. Brooks and a conjecture of H. Hadwiger”, Proc. London Math. Soc. (3), 7:3 (1957), 161–195 | DOI | MR | Zbl

[13] Dirac G. A., “The number of edges in critical graphs”, J. Reine Angew. Math., 268–269 (1974), 150–164 | MR | Zbl

[14] Dvořák Z., Postle L., List-Coloring Embedded Graphs Without Cycles of Lengths $4$ to $8$, 2015, arXiv: 1508.03437

[15] Erdős P., Rubin A. L., Taylor H., “Choosability in Graphs”, Proc. West Coast Conf. on Combinatorics, Graph Theory, and Computing, Congressus Numerantium XXVI, 1979, 125–157 | MR

[16] Galvin F., “The list chromatic index of a bipartite multigraph”, J. Combin. Theory Ser. B, 63 (1995), 153–158 | DOI | MR | Zbl

[17] Jensen T. R., Toft B., “12.20 List-edge-chromatic numbers”, Graph Coloring Problems, Wiley-Interscience, New York, 1995, 201–202 | MR

[18] Johansson A., Asymptotic choice number for triangle free graphs, Technical Report, DIMACS, 1996, 91–95

[19] Kostochka A. V., Stiebitz M., “A list version of Dirac's theorem on the number of edges in colour-critical graphs”, J. Graph Theory, 39:3 (2002), 165–177 | DOI | MR | Zbl

[20] Molloy M., The List Chromatic Number of Graphs with Small Clique Number, 2017, arXiv: 1701.09133 | MR

[21] Shannon C. E., “A theorem on coloring the lines of a network”, J. Math. Phys., 28 (1949), 148–151 | DOI | MR | Zbl

[22] Thomassen C., “Every planar graph is $5$-choosable”, J. Combin. Theory, Ser. B, 62:1 (1994), 180–181 | DOI | MR | Zbl

[23] Thomassen C., “$3$-list-coloring planar graphs of girth $5$”, J. Combin. Theory, Ser. B, 64:1 (1995), 101–107 | DOI | MR | Zbl