# Conditions for ß-perfectness

J.C.M. Keijsper, M. Tewes

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

55 Downloads (Pure)

## Samenvatting

A ß-perfect graph is a simple graph G such that ¿(G') = ß(G') for every induced subgraph G' of G, where ¿(G') is the chromatic number of G', and ß(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., d(H)+1). The vertices of a ß-perfect graph G can be coloured with ¿(G) colours in polynomial time (greedily). 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.
Originele taal-2 Engels 123-148 Discussiones Mathematicae - Graph Theory 22 1 Gepubliceerd - 2002

## Vingerafdruk

Duik in de onderzoeksthema's van 'Conditions for ß-perfectness'. Samen vormen ze een unieke vingerafdruk.