EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

On Strongly and Robustly Critical Graphs

Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →