Score vectors and tournaments with cyclic chromatic number 1 or 2
type: Item
instance of: scholarly article
zbMATH Open document ID: 0963.05062
publication date: 2001-06-10T00:00:00Z
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1602747
zbMATH Keywords: tournament
zbMATH Keywords: cyclic chromatic number
zbMATH Keywords: score vector
MaRDI profile type: Publication
author: S. Ao
author: D. Hanson
title: Score vectors and tournaments with cyclic chromatic number 1 or 2
published in: Ars Combinatoria
review text: 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.
reviewed by: Zdeněk Ryjáček
description: scientific article