Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Conditions for β-perfectness

100%

Keijsper J., Tewes M.

Discussiones Mathematicae Graph Theory

2002

tom 22

nr 1

123-148

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., δ(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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Keijsper J.

1 Tewes M.

1 2002

Wyniki wyszukiwania

Conditions for β-perfectness