On the Minimum Number of Edges Giving Maximum Oriented Chromatic Number

We show that the minimum number of edges in a graph on n vertices with oriented chromatic number n is (1 + o(1))n log 2 n. In 1995, in a conversation with the French member of the set of the authors of this note, P'al Erdos asked about the minimal number of edges a graph on n vertices with oriented chromatic number n can have. During the conference on the Future of Discrete Mathematics in the cosy but fruitful atmosphere of the Stir'in Castle we found an elementary answer to this question which we present below. Novosibirsk State University, Novosibirsk, Russia 630090. Research partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research and by the Cooperative Grant Award RM1-181 of the US Civilian Research and Development Foundation. y Department of Discrete Mathematics, Adam Mickiewicz University, 60-769 Pozna'n, Poland. Research partially supported by KBN grant 2 P03A 023 09. z Mathematical Institute of the Hungarian Academy of Sciences, P..