×

On 2-defective DP-colorings of sparse graphs. (English) Zbl 1458.05074

Summary: Introduced by Z. Dvořák and L. Postle [J. Comb. Theory, Ser. B 129, 38–54 (2018; Zbl 1379.05034)], the notion of DP-coloring generalizes list coloring and helps to prove new results on list coloring. We consider 1-defective and 2-defective DP-colorings of graphs with 2 colors. For \(j=1,2\), we find exact lower bounds on the number of edges in \((j,2)\)-DP-critical graphs (that is, graphs that do not admit \(j\)-defective DP-colorings with 2 colors but whose every proper subgraph has such a coloring) with a given number of vertices. These bounds also hold for \((j,2)\)-list-critical graphs, and for \(j=2\) are better than previously known bounds by F. Havet and J.-S. Sereni [J. Graph Theory 52, No. 3, 181–199 (2006; Zbl 1104.05026)].

MSC:

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archdeacon, D., A note on defective colorings of graphs in surfaces, J. Graph Theory, 11, 517-519 (1987) · Zbl 0654.05030
[2] Bernshteyn, A.; Kostochka, A.; Pron, S., On DP-coloring of graphs and multigraphs, Sib. Math. J., 58, 1, 28-36 (2017) · Zbl 1366.05038
[3] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Ochem, P.; Raspaud, A., Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\), J. Graph Theory, 65, 83-93 (2010) · Zbl 1209.05177
[4] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Raspaud, A., \( ( k , j )\)-Coloring of sparse graphs, Discrete Appl. Math., 159, 1947-1953 (2011) · Zbl 1239.05059
[5] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Raspaud, A., \( ( k , 1 )\)-Coloring of sparse graphs, Discrete Math., 312, 1128-1135 (2012) · Zbl 1238.05084
[6] Borodin, O. V.; Kostochka, A. V., Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1, Sib. Math. J., 52, 5, 1004-1010 (2011) · Zbl 1232.05073
[7] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041
[8] Borodin, O. V.; Kostochka, A. V.; Yancey, M., On 1-improper 2-coloring of sparse graphs, Discrete Math., 313, 22, 2638-2649 (2013) · Zbl 1281.05060
[9] Cowen, L. J.; Cowen, R.; Woodall, D. R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 187-195 (1986) · Zbl 0596.05024
[10] Cushing, W.; Kierstead, H. A., Planar graphs are 1-relaxed 4-choosable, European J. Combin., 31, 1385-1397 (2010) · Zbl 1221.05077
[11] Dorbec, P.; Kaiser, T.; Montassier, M.; Raspaud, A., Limits of near-coloring of sparse graphs, J. Graph Theory, 75, 191-202 (2014) · Zbl 1280.05040
[12] Dvořák, Z.; Postle, L., Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B, 129, 38-54 (2018) · Zbl 1379.05034
[13] Eaton, N.; Hull, T., Defective list colorings of planar graphs, Bull. Inst. Combin. Appl., 25, 79-87 (1999) · Zbl 0916.05026
[14] Edwards, K.; Kang, D. Y.; Kim, J.; i. Oum, S.; Seymour, P., A relative of Hadwiger’s conjecture, SIAM J. Discrete Math., 29, 2385-2388 (2015) · Zbl 1328.05063
[15] Esperet, L.; Montassier, M.; Ochem, P.; Pinlou, A., A complexity dichotomy for the coloring of sparse graphs, J. Graph Theory, 73, 85-102 (2013) · Zbl 1264.05049
[16] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 181-199 (2006) · Zbl 1104.05026
[17] Hendrey, K.; Wood, D., Defective and clustered choosability of sparse graphs (2018), arXiv:1806.07040 preprint · Zbl 1436.05038
[18] Kim, J.; Kostochka, A. V.; Zhu, X., Improper coloring of sparse graphs with a given girth, I: \( ( 0 , 1 )\)-colorings of triangle-free graphs, European J. Combin., 42, 26-48 (2014) · Zbl 1297.05083
[19] Kim, J.; Kostochka, A. V.; Zhu, X., Improper coloring of sparse graphs with a given girth, II: Constructions, J. Graph Theory, 81, 403-413 (2015) · Zbl 1333.05115
[20] Kopreski, M.; Yu, G., Maximum average degree and relaxed coloring, Discrete Math., 340, 2528-2530 (2017) · Zbl 1367.05075
[21] Lovász, L., On decomposition of graphs, Studia Sci. Math. Hungar., 1, 237-238 (1966) · Zbl 0151.33401
[22] Ossona de Mendez, P.; Oum, S.-I.; Wood, D. R., Defective colouring of graphs excluding a subgraph or minor, Combinatorica, 39, 377-410 (2019) · Zbl 1438.05102
[23] Sittitrai, P.; Nakprasit, K., Analogue of DP-coloring on variable degeneracy and its applications on list vertex-arboricity and DP-coloring (2018), preprint
[24] Van den Heuvel, J.; Wood, D. R., Improper colourings inspired by Hadwiger’s conjecture, J. Lond. Math. Soc., 98, 129-148 (2018) · Zbl 1402.05085
[25] Škrekovski, R., List improper colourings of planar graphs, Combin. Probab. Comput., 8, 293-299 (1999) · Zbl 0940.05031
[26] Škrekovski, R., List improper colorings of planar graphs with prescribed girth, Discrete Math., 214, 221-233 (2000) · Zbl 0940.05027
[27] Wood, D. R., Defective and clustered graph colouring, Electron. J. Combin. (2018), #DS23 · Zbl 1391.05119
[28] Woodall, D. R., Defective choosability of graphs in surfaces, Discuss. Math. Graph Theory, 31, 441-459 (2011) · Zbl 1229.05107
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.