[HTML][HTML] Coloring tournaments: From local to global

A Harutyunyan, TN Le, S Thomassé, H Wu - Journal of Combinatorial …, 2019 - Elsevier
Journal of Combinatorial Theory, Series B, 2019Elsevier
The 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 note 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 …
The 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 note 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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果