P.Erdos的一个问题

On a Problem of P.Erods

P.Erods在[1]中提出一个问题“设图G的围长g(G)≥4,图G能否这样定向:使图G不包含有向圈,而且任意改变它的某一条边的方向后所得图也不包含有向圈”。本文证明了二部图,三部图可以这样定向,也构造并证明了一类图Q2t+1不能这样定向。

P.Erdos put forward a question in [1] 揕et g(G)≥4, Can G be oriented in such a way that it contains no directed cycle and if we reverse the direction of any one of its edges the resulting graph does not contain a directed cycle either??In this paper, we will see that for many graphs, for example the 2-partite graphs and the 3- partite graphs the answer of this question is Yes, but we will see that the answer for some of other graphs, denoted by Q2t+1 is false.