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 a 3 …

We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph
as a topological minor. For a digraph F, denote by mader χ→(F) the smallest integer k such …

We prove a conjecture by Aboulker, Charbit, and Naserasr by showing that every oriented
graph in which the out‐neighborhood of every vertex induces a transitive tournament can be …

Two subgraphs A, B of a graph G are anticomplete if they are vertex-disjoint and there are
no edges joining them. Is it true that if G is a graph with bounded clique number, and …

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 …

Heroes in Orientations of Chordal Graphs Page 1 Copyright © by SIAM. Unauthorized
reproduction of this article is prohibited. SIAM J. DISCRETE MATH. © 2022 Society for Industrial …

Many well-known NP-hard algorithmic problems on directed graphs resist efficient
parameterizations with most known width measures for directed graphs, such as directed …

This paper is a survey of results and problems related to the following question: is it true that
if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint …

Abstract In k-Digraph Coloring we are given a digraph and are asked to partition its vertices
into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as …

The dichromatic number χ→(D) χ(D) of a digraph DD is the smallest kk for which it admits ak
k‐coloring where every color class induces an acyclic subgraph. Inspired by Hadwiger's …