Coloring Tournaments with Few Colors: Algorithms and Complexity
Felix Klingelhoefer, Alantha Newman · SIAM Journal on Discrete Mathematics · 2024
Abstract. A [Formula: see text] -coloring of a tournament is a partition of its vertices into [Formula: see text] acyclic sets. Deciding if a tournament is 2-colorable is NP -hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds. We present a new efficient decomposition lemma for tournaments, which we use to design polynomial-time algorithms to color various classes of tournaments with few colors, notably to color a 2-colorable tournament with 10 colors. We also use this lemma to prove equivalence between the problems of coloring 3-colorable tournaments and coloring 3-colorable graphs with constantly many colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.