The dichromatic number χ(D) of a digraph is the minimum number k such that V(D) can be partitioned into k subsets, each inducing an acyclic digraph. The acyclic number α(D) is the cardinality of a largest induced acyclic subdigraph of D. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating χ and α remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every ε > 0, it is hard to approximate both α and χ up to a factor of n^{1-ε} even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color 𝓁-dicolorable digraphs using at most 𝓁 ⋅ n^{1-1/(𝓁)} colors in time O(n^{2𝓁}); in particular, we can color 2-dicolorable digraphs with 2√n colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number α of the underlying graph. We consider two special cases in this regard: digraphs with χ(D) ≤ 2 and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.

As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is no PTAS for finding the largest complete minor unless P = NP, whereas the best known result is a polytime O(√ n)-approximation algorithm by Alon, Lingas and Wahlén. We investigate the complexity of finding K_t as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime f(t)-approximation algorithm, where f is triply exponential in t but independent of n. The algorithm is based on delayed decompositions and shows that ordered graphs without a K_t interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding K_t as an interval minor have bounded chromatic number.