2022/01/31 by Barát, János, Czett, Mátyás
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.13161
The dichromatic number of a directed graph is at most 2, if we can 2-color the vertices such that each monochromatic part is acyclic. An oriented graph arises from a graph by orienting its edges in one of the two possible directions. We study oriented graphs, which have dichromatic number more than 2. Such a graph D is 3-dicritical if the removal of any arc of D reduces the dichromatic number to 2. We construct infinitely many 3-dicritical oriented graphs. Neumann-Lara found the four 7-vertex 3-dichromatic tournaments. We determine the 8-vertex 3-dichromatic tournaments, which do not contain any of these, there are 64 of them. We also find all 3-dicritical oriented graphs on 8 vertices, there are 159 of them. We determine the smallest number of arcs that a 3-dicritical oriented graph can have. There is a unique oriented graph with 7 vertices and 20 arcs.