Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 5 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

A Note on Vertex-Critical Induced Subgraphs of Shift Graphs

  • Tomáš Kaiser
  • Matěj Stehlík
  • Riste Škrekovski
  • Bjarne Toft
Open at sourcePDFDOICite

Abstract

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 surprising property: for each integer k ≥ 1, the smallest k-chromatic shift graph contains a unique induced k-vertex-critical subgraph. We give an explicit description of this subgraph and prove its uniqueness. This provides a new family of vertex-critical triangle-free graphs of arbitrarily large chromatic number.

Related

  1. On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
    Elizaveta Popova
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Contractable 2-connected subgraphs in minimally 3-connected graphs
    Rongchuan Tao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Large induced subgraphs with k vertices of maximum degree
    Zhen liu, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A proof of Vince's conjecture on the average order of connected induced subgraphs
    Jungang Chen, Hongxia Ma
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On extending induced subgraphs
    Guoli Ding, Jake Weber, Weihao Xia
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{kaiser2026note,
  title = {{A Note on Vertex-Critical Induced Subgraphs of Shift Graphs}},
  author = {Tomáš Kaiser and Matěj Stehlík and Riste Škrekovski and Bjarne Toft},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/15178},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33p413},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
AU  - Tomáš Kaiser
AU  - Matěj Stehlík
AU  - Riste Škrekovski
AU  - Bjarne Toft
PY  - 2026
DA  - 2026/10/23
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/15178
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33p413
AB  - 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 surprising property: for each integer k ≥ 1, the smallest k-chromatic shift graph contains a unique induced k-vertex-critical subgraph. We give an explicit description of this subgraph and prove its uniqueness. This provides a new family of vertex-critical triangle-free graphs of arbitrarily large chromatic number.
SN  - 1077-8926
ER  -