Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2408.04538 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912927106203648 |
|---|---|
| author | Bernshteyn, Anton Kaul, Hemanshu Mudrock, Jeffrey A. Sharma, Gunjan |
| author_facet | Bernshteyn, Anton Kaul, Hemanshu Mudrock, Jeffrey A. Sharma, Gunjan |
| contents | 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 $k$-critical yet $L$-colorable with respect to every non-constant assignment $L$ of lists of size $k-1$. Here we strengthen this notion and extend it to the framework of DP-coloring (or correspondence coloring) by defining robustly $k$-critical graphs as those that are not $(k-1)$-DP-colorable, but only due to the fact that $χ(G) = k$. We then seek general methods for constructing robustly critical graphs. Our main result is that if $G$ is a critical graph (with respect to ordinary coloring), then the join of $G$ with a sufficiently large clique is robustly critical; this is new even for strong criticality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On strongly and robustly critical graphs Bernshteyn, Anton Kaul, Hemanshu Mudrock, Jeffrey A. Sharma, Gunjan Combinatorics 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 $k$-critical yet $L$-colorable with respect to every non-constant assignment $L$ of lists of size $k-1$. Here we strengthen this notion and extend it to the framework of DP-coloring (or correspondence coloring) by defining robustly $k$-critical graphs as those that are not $(k-1)$-DP-colorable, but only due to the fact that $χ(G) = k$. We then seek general methods for constructing robustly critical graphs. Our main result is that if $G$ is a critical graph (with respect to ordinary coloring), then the join of $G$ with a sufficiently large clique is robustly critical; this is new even for strong criticality. |
| title | On strongly and robustly critical graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.04538 |