The 3 and 4-dichromatic tournaments of minimum order. (English) Zbl 0829.05028

Author’s abstract: The dichromatic number \(\text{dc} (D)\) of a digraph \(D\) is the minimum number of acyclic sets in which \(V(D)\) can be partitioned. If \(\text{dc}(D) = r\), \(D\) is called \(r\)-dichromatic. It is proved that the minimum order of a 3-dichromatic (resp. 4-dichromatic) tournament is 7 (resp. 11). It is also proved that there are exactly four nonisomorphic 3-dichromatic tournaments of order 7 and a unique 4- dichromatic tournament of order 11. All these tournaments are characterized.


05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI


[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier: American Elsevier New York · Zbl 1134.05001
[2] Erdős, P., Problems and results in number theory and graph theory, Proc. 9th Manitoba Conf. Numer. Math. and Computing, 3-21 (1979)
[3] Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar, 9, 125-132 (1964), Acad. Sci. · Zbl 0136.44901
[5] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 265-270 (1982) · Zbl 0506.05031
[6] Neumann-Lara, V.; Urrutia, J., Vertex critical \(r\)-dichromatic tournaments, Discrete Math., 40, 83-87 (1984) · Zbl 0532.05031
[7] Reid, K. B.; Parker, E. T., Disproof of a conjecture of Erdős and Moser on tournaments, J. Combin. Theory, 9, 225-238 (1970) · Zbl 0204.24605
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.