zbMATH — the first resource for mathematics

DP-colorings of graphs with high chromatic number. (English) Zbl 1369.05065
Summary: DP-coloring is a generalization of list coloring introduced recently by Z. Dvořák and L. Postle [“Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, Preprint, arXiv:1508.03437]. We prove that for every \(n\)-vertex graph \(G\) whose chromatic number \(\chi(G)\) is “close” to \(n\), the DP-chromatic number of \(G\) equals \(\chi(G)\). “Close” here means \(\chi(G) \geq n-O(\sqrt{n})\), and we also show that this lower bound is best possible (up to the constant factor in front of \(\sqrt{n}\)), in contrast to the case of list coloring.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[2] A. Bernshteyn, A. Kostochka, On differences between DP-coloring and list coloring, 2017. arXiv:1705.04883, preprint · Zbl 1366.05038
[3] Z. Dvořák, L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths \(4\) to \(8\), 2015. arXiv:1508.03437, preprint
[4] Enomoto, H.; Ohba, K.; Ota, K.; Sakamoto, J., Choice number of some complete multi-partite graphs, Discrete Math., 244, 1-3, 55-66, (2002) · Zbl 0994.05066
[5] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer. XXVI (1979) 125-157
[6] Noel, J. A.; Reed, B. A.; Wu, H., A proof of a conjecture of ohba, J. Graph Theory, 79, 86-102, (2015) · Zbl 1320.05045
[7] Ohba, K., On chromatic-choosable graphs, J. Graph Theory, 40, 130-135, (2002) · Zbl 1004.05030
[8] Thomassen, C., Every planar graph is \(5\)-choosable, J. Combin. Theory Ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[9] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. Combin. Theory Ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[10] Vizing, V. G., Vertex colorings with given colors, Diskret. Analiz., 29, 3-10, (1976), (in Russian) · Zbl 1249.90303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.