A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments. (English) Zbl 1185.05071

Summary: We exhibit infinite families of vertex critical \(r\)-dichromatic circulant tournaments for all \(r \geq 3\). The existence of these infinite families was conjectured by Neumann-Lara [V. Neumann-Lara, “Vertex critical 4-dichromatic circulant tournaments”, Discrete Math. 170, No. 1-3, 289–291 (1997; Zbl 0876.05039)], who later proved it for all \(r \geq 3\) and \(r \neq 7\). Using different methods, we provide new constructions of such infinite families for all \(r \geq 3\), which covers the case \(r = 7\) and thus settles the conjecture.


05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C63 Infinite graphs


Zbl 0876.05039
Full Text: DOI


[1] Beineke, L.W.; Reid, K.B., Tournaments, (), 169-204 · Zbl 0434.05037
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier Pub. Co · Zbl 1134.05001
[3] Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings, Magyar tud. akad. mat. int. kutató int. Közl., 9, 125-132, (1964) · Zbl 0136.44901
[4] B. Llano, M. Olsen, On a conjecture of Víctor Neumann-Lara (submitted for publication) · Zbl 1341.05101
[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., The 3- and 4-dichromatic tournaments of minimum order, Discrete math., 135, 233-243, (1994) · Zbl 0829.05028
[7] Neumann-Lara, V., Note on vertex critical 4-dichromatic circulant tournaments, Discrete math., 170, 289-291, (1997) · Zbl 0876.05039
[8] Neumann-Lara, V., The acyclic disconnection of a digraph, Discrete math., 617-632, (1999), 197/198 · Zbl 0928.05033
[9] Neumann-Lara, V., Dichromatic number, circulant tournaments and zykov sums of digraphs, Discuss. math. graph theory, 2, 197-207, (2000) · Zbl 0984.05043
[10] Neumann-Lara, V.; Urrutia, J., Vertex critical r-dichromatic tournaments, Discrete math., 49, 83-87, (1994) · Zbl 0532.05031
[11] 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
[12] Sanchez-Flores, A., On tournaments free of large transitive subtournaments, Graphs and combinatorics, 14, 181-200, (1998) · Zbl 0918.05058
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.