Coloring tournaments: from local to global

DOI10.1016/J.JCTB.2019.01.005zbMATH Open1415.05064arXiv1702.01607OpenAlexW2607410332WikidataQ128482824 ScholiaQ128482824MaRDI QIDQ2312616

Author name not available (Why is that?)

Publication date: 17 July 2019

Published in: (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1702.01607

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Coloring tournaments: from local to global

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312616)