A note on vertex-critical induced subgraphs of shift graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917219330424832 |
|---|---|
| author | Kaiser, Tomáš Stehlík, Matěj Škrekovski, Riste |
| author_facet | Kaiser, Tomáš Stehlík, Matěj Škrekovski, Riste |
| contents | Shift graphs, introduced by Erdős and Hajnal in 1964, form one of the simplest known non-recursive constructions of triangle-free graphs with arbitrarily large chromatic number. In this note, we identify a suprising property: for each integer $k \geq 1$, the smallest $k$-chromatic shift graph contains a unique $k$-vertex-critical subgraph. We give an explicit description of this subgraph and prove its uniqueness. This provides a new and remarkably simple family of triangle-free vertex-critical graphs of arbitrarily large chromatic number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16342 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on vertex-critical induced subgraphs of shift graphs Kaiser, Tomáš Stehlík, Matěj Škrekovski, Riste Combinatorics 05C15 Shift graphs, introduced by Erdős and Hajnal in 1964, form one of the simplest known non-recursive constructions of triangle-free graphs with arbitrarily large chromatic number. In this note, we identify a suprising property: for each integer $k \geq 1$, the smallest $k$-chromatic shift graph contains a unique $k$-vertex-critical subgraph. We give an explicit description of this subgraph and prove its uniqueness. This provides a new and remarkably simple family of triangle-free vertex-critical graphs of arbitrarily large chromatic number. |
| title | A note on vertex-critical induced subgraphs of shift graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2601.16342 |