Coloring tournaments: From local to global
| Autor: | Tien-Nam Le, Ararat Harutyunyan, Stéphan Thomassé, Hehui Wu |
|---|---|
| Přispěvatelé: | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Shanghai Center for Mathematical Sciences, Fudan University, Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2019 |
| Předmět: |
0102 computer and information sciences
01 natural sciences Theoretical Computer Science Combinatorics Computer Science::Discrete Mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics [INFO]Computer Science [cs] Tournament Chromatic scale [MATH]Mathematics [math] 0101 mathematics Undirected graph Mathematics Discrete mathematics Transitive relation Mathematics::Combinatorics 010102 general mathematics Erdős–Hajnal conjecture Directed graph Vertex (geometry) Digraph coloring Computational Theory and Mathematics 010201 computation theory & mathematics Independent set Combinatorics (math.CO) Chromatic number of tournaments |
| Zdroj: | Journal of Combinatorial Theory, Series B Journal of Combinatorial Theory, Series B, Elsevier, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩ Journal of Combinatorial Theory, Series B, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩ |
| ISSN: | 0095-8956 1096-0902 |
| DOI: | 10.1016/j.jctb.2019.01.005 |
| Popis: | 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. Comment: 7 pages, no figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect