On Strongly and Robustly Critical Graphs
Journal of Graph Theory · 2026-08 · 112 (4) · 469-483
DOI: 10.1002/jgt.70033 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 16.04.2026. Verfasst von Anton Bernshteyn und 3 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list‐critical graphs occupy a prominent place in graph coloring theory. Stiebitz, Tuza, and Voigt introduced strongly critical graphs, i.e., graphs that are ‐critical yet ‐colorable with respect to every non‐constant assignment of lists of size . Here we strengthen this notion and extend it to the framework of DP‐coloring (or correspondence coloring) by defining robustly ‐critical graphs as those that are not ‐DP‐colorable, but only due to the fact that . We then seek general methods for constructing robustly critical graphs. Our main result is that if is a critical graph (with respect to ordinary coloring), then the join of with a sufficiently large clique is robustly critical; this is new even for strong criticality.
Förderung
- National Science Foundation
Zitieren
APA
Bernshteyn, A., Kaul, H., Mudrock, J. A., & Sharma, G. (2026). On Strongly and Robustly Critical Graphs. Journal of Graph Theory, 112(4), 469-483. https://doi.org/10.1002/jgt.70033
Vancouver
Bernshteyn A, Kaul H, Mudrock JA, Sharma G. On Strongly and Robustly Critical Graphs. Journal of Graph Theory. 2026;112(4):469-483. doi:10.1002/jgt.70033
BibTeX
@article{Bernshteyn2026,
author = {Bernshteyn, Anton and Kaul, Hemanshu and Mudrock, Jeffrey A. and Sharma, Gunjan},
title = {On Strongly and Robustly Critical Graphs},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {4},
pages = {469--483},
doi = {10.1002/jgt.70033}
}
EUVIMED