Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Generalized colorings and avoidable orientations

100%

Szigeti J., Tuza Z.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 1

137-145

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Szigeti J.

1 Tuza Z.

1 1997

Wyniki wyszukiwania

Generalized colorings and avoidable orientations