ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 22(1) (2002) 123-148DOI: 10.7151/dmgt.1163
University of Twente
Faculty of Mathematical Sciences
7500 AE Enschede, The Netherlands
Faculty of Mathematics and Computer Sciences
09596 Freiberg, Germany
The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden
induced subgraphs, for a graph to be β-perfect. We give new sufficient conditions
and make improvements to sufficient conditions previously given by others. We also mention a necessary
condition which generalizes the fact that no β-perfect graph contains an even hole.
Keywords: chromatic number, colouring number, polynomial time.
2000 Mathematics Subject Classification: 05C15, 05C75.
Received 10 August 2000
Revised 3 July 2001