Vertex-critical subgraphs of Kneser-graphs

A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We show that if the stable (independent) n-subsets of a circuit wit 2n+k vertices are split into k+1 classes, one of the classes contains two disjoint n-subsets; this yields a (k+2)-vertex-critical subgraph of Lovász 's Kneser-graph KG n,k.
Original languageEnglish
Pages (from-to)454-461
Number of pages8
JournalNieuw Archief voor Wiskunde
Volume26
Issue number3
Publication statusPublished - 1978

Fingerprint Dive into the research topics of 'Vertex-critical subgraphs of Kneser-graphs'. Together they form a unique fingerprint.

Cite this