Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Coloring tournaments: from local to global   The \emph{chromatic number} of a directed graph $D$ is the minimum number of
colors needed to color the vertices of $D$ such that each color class of $D$
induces an acyclic subdigraph. Thus, the chromatic number of a tournament $T$
is the minimum number of transitive subtournaments which cover the vertex set
of $T$. We show in this paper that tournaments are significantly simpler than
graphs with respect to coloring. Indeed, while undirected graphs can be
altogether "locally simple" (every neighborhood is a stable set) and have large
chromatic number, we show that locally simple tournaments are indeed simple. In
particular, there is a function $f$ such that if the out-neighborhood of every
vertex in a tournament $T$ has chromatic number at most $c$, then $T$ has
chromatic number at most $f(c)$. This answers a question of Berger et al.

27
The categories of this paper are: comp-gas
22
The categories of this paper are: chao-dyn
7
The categories of this paper are: hep-th
19
The categories of this paper are: eess
4
The categories of this paper are: cond-mat
0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
36
The categories of this paper are: cmp-lg
10
The categories of this paper are: q-bio
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
28
The categories of this paper are: alg-geom