CLASSES OF STABLE SUBGRAPHS IN TRANSITIVE ORIENTATION OF THE GRAPH

Sergiu CATARANCIUC, Nicolae GRIGORIU Universitatea de Stat din Moldova

Abstract

In the article there are analyzed the classes of the stable subgraphs, used for characterization of transitively orientable graphs and their properties. The subgraphs that we describe in this paper are a support for the constructions of the transitive orientation of the graph, as well as the formula for the number of transitive orientations in a graph. In addition, we present necessary and sufficient conditions for a graph to be transitively orientable. Keywords: transitively orientable graph, stable subgraph, non-triangulated chain, minimal stable subgraph, B-stable subgraph, graph factor.