Vertex-critical subgraphs of Kneser-graphs

A. Schrijver

Vertex-critical subgraphs of Kneser-graphs

A. Schrijver

Mathematics and Computer Science

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	454-461
Number of pages	8
Journal	Nieuw Archief voor Wiskunde
Volume	26
Issue number	3
Publication status	Published - 1978

Cite this

@article{0b98e551aae34e3090a17c4e08c5afa2,

title = "Vertex-critical subgraphs of Kneser-graphs",

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{\'a}sz 's Kneser-graph KG n,k.",

author = "A. Schrijver",

year = "1978",

language = "English",

volume = "26",

pages = "454--461",

journal = "Nieuw Archief voor Wiskunde",

issn = "0028-9825",

number = "3",

}

TY - JOUR

T1 - Vertex-critical subgraphs of Kneser-graphs

AU - Schrijver, A.

PY - 1978

Y1 - 1978

N2 - 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.

AB - 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.

M3 - Article

SN - 0028-9825

VL - 26

SP - 454

EP - 461

JO - Nieuw Archief voor Wiskunde

JF - Nieuw Archief voor Wiskunde

IS - 3

ER -

Vertex-critical subgraphs of Kneser-graphs

Abstract

Fingerprint

Cite this