Alternating orientation and alternating colouration of perfect graphs (Q1089007)

In this note are introduced the terms of alternating orientation of graphs and alternating colouration of graphs, and at first in Theorem 2.2 the important property is proved that in a minimal imperfect graph each path \(P_ 3\) with three vertices extends into a hole. By using this property the author generates two classes of perfect graphs and he shows: - Every alternately orientable graph is perfect (Theorem 2.1), - Every alternately colourable graph is perfect (Theorem 5.1). It is shown that the first class contains all comparability graphs, all triangulated graphs, the i-triangulated graphs and such graphs G which are union of two threshold graphs, and the second class contains all triangulated graphs and all line-graphs of bipartite graphs. All these terms are defined and they are described in a clear manner. Furthermore it is shown that certain well-known classes of perfect graphs are not alternately orientable, and vice versa. Finally the author develops an algorithm which allows to determine whether a graph is alternately orientable respectively alternately colourable.