# Algorithms for Promise Coloring Problems on Tournaments and Graphs

- Authors
- Publication Date
- Dec 04, 2023
- Source
- Hal-Diderot
- Keywords
- Language
- English
- License
- Unknown
- External links

## Abstract

The first part of this thesis is on the subject of coloring tournaments, from analgorithmic, complexity and structural perspective. A k-coloring of a directed graph,and in particular a tournament, is a partition of its vertices into k acyclic sets. Thechromatic number of a directed graph or a tournament is then the minimum k suchthat it is k-colorable. Deciding if a tournament is 2-colorable is already NP-hard.A natural problem, akin to that of coloring a 3-colorable graph with few colors, isto color a 2-colorable tournament with few colors. This problem does not seem tohave been addressed before, although it is a special case of coloring a 2-colorable3-uniform hypergraph with few colors, which is a well-studied problem withsuper-constant lower bounds.We present an efficient decomposition lemma for tournaments and show that itcan be used to design polynomial-time algorithms to color various classes oftournaments with few colors, including an algorithm to color a 2-colorable tournamentwith ten colors. For the classes of tournaments considered, we complement ourupper bounds with strengthened lower bounds, painting a comprehensive picture of thealgorithmic and complexity aspects of coloring tournaments. We then extend ourresults to different classes of tournaments and digraphs.The neighborhood of an arc uv in a tournament T is the set of vertices that forma directed triangle with arc uv. By using our decomposition lemma, we show thatif the neighborhood of every arc in a tournament has bounded chromatic number,then the whole tournament has bounded chromatic number. This holds moregenerally for oriented graphs with bounded independence number, and we extend ourproof from tournaments to this class of dense digraphs. As an application, we provethe equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture ofNguyen, Scott and Seymour relating the structure of graphs and tournaments withhigh chromatic number.In the second part of this thesis, we focus on the problem of finding maximumstable sets in the class of Cycle-plus-Triangles graphs. A Cycle-plus-Trianglesgraph is the disjoint union of t triangles and a Hamilton cycle on the3t vertices. It is 3-colorable, and we give an overview of the different proofs of its3-colorability. There is, however, no known efficient algorithm to find a 3-coloring oreven to find a maximum stable set (i.e., a stable set of size t).We present a simple randomized algorithm that outputs a maximum stable setupon termination. We conjecture that for any Cycle-plus-Triangles instance,our algorithm terminates in expected polynomial time. In an (unsuccessful) effort tofind hard instances for our algorithm, we discuss structure and properties ofCycle-plus-Triangles instances and methods for generating them. Finally we examinethe behavior of these algorithms on related problems, such as 3-coloring, or findingmaximum independent sets in a more general class of graphs.