About skew partitions in minimal imperfect graphs

Authors
Roussel, F Rubio, P
Citation
F. Roussel et P. Rubio, About skew partitions in minimal imperfect graphs, J COMB TH B, 83(2), 2001, pp. 171-190
Citations number
12
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
83
Issue
2
Year of publication
2001
Pages
171 - 190
Database
ISI
SICI code
0095-8956(200111)83:2<171:ASPIMI>2.0.ZU;2-A
Abstract
V. Chvatal conjectured in 1985 that a minimal imperfect graph G cannot have a skew cutset (i.e., a cutset S decomposable into disjoint sets A and B jo ined by all possible edges). We prove here the conjecture in the particular case where at least one of A and B is a stable set. (C) 2001 Academic Pres s.