2 papers
cs.DS2024
Coloring tournaments with few colors: Algorithms and complexity
Felix Klingelhoefer, Alantha Newman
A -coloring of a tournament is a partition of its vertices into acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring…
math.CO2024
Bounding the chromatic number of dense digraphs by arc neighborhoods
Felix Klingelhoefer, Alantha Newman
The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is th…