Score vectors and tournaments with cyclic chromatic number 1 or 2 (Q2713613)

The score vector of an \(n\)-tournament \(T_n\) is the non-decreasing sequence of outdegrees of its vertices. The cyclic chromatic number \(\chi _c(T_n)\) is the minimum number of colors to color the vertices of \(T_n\) such that no copy of the cycle \(C_3\) in \(T_n\) is monochromatic. The main result of the paper shows that for any vector \(S=(s_1,s_2,\ldots ,s_n)\) with \(s_1\leq s_2\leq \ldots \leq s_n\) there is a partition \(V(T_n)=V_1\cup V_2\) such that both \(V_1\) and \(V_2\) induce a transitive subtournament of \(T_n\). This implies that for any score vector \(S\) there is a tournament \(T\) with \(\chi _c(T)\leq 2\), proving a conjecture by Bagga, Beineke and Harary.