zbMATH — the first resource for mathematics

Infinite families of \((n+1)\)-dichromatic vertex critical circulant tournaments. (English) Zbl 1291.05078
Hliněný, Petr (ed.) et al., 6th Czech-Slovak international symposium on combinatorics, graph theory, algorithms and applications, DIMATIA Center, Charles University, Prague, Czech Republic, July 10–16, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 28, 141-144 (2007).
Summary: In this talk we expose the results about infinite families of vertex critical \(r\)-dichromatic circulant tournaments for all \(r\geq 3\). The existence of these infinite families was conjectured by V. Neumann-Lara [Discrete Math. 170, No. 1–3, 289–291 (1997; Zbl 0876.05039)], who later proved it for all \(r\geq 3\) and \(r\not= 7\). Using different methods we find explicit constructions of these infinite families for all \(r\geq 3\), including the case when \(r=7\), which complete the proof of the conjecture.
For the entire collection see [Zbl 1109.05007].
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Beineke, L.W.; Reid, K.B., Tournaments, Selected topics in graph theory, (1979), Academic Press, 169-204
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier Pub. Co. · Zbl 1226.05083
[3] Llano B., Olsen M., On a conjecture of Neumann-Lara, (in preparation)
[4] Neumann-Lara, V., The dichromatic number of a digraph, J. combin. theory ser., 33, 265-270, (1982) · Zbl 0506.05031
[5] Neumann-Lara, V., The 3-and 4-dichromatic tournaments of minimum order, Discrete math., 135, 233-243, (1994) · Zbl 0829.05028
[6] Neumann-Lara, V., Note on vertex critical 4-dichromatic circulant tournaments, Discrete math., 170, 289-291, (1997) · Zbl 0876.05039
[7] Neumann-Lara, V., The acyclic disonnection of a digraph, Discrete math., 197/198, 617-632, (1999) · Zbl 0928.05033
[8] Neumann-Lara, V., Dichromatic number, circulant tournaments and zykov sums of digraphs, Discuss. math. graph theory, 20, 197-207, (2000) · Zbl 0984.05043
[9] Neumann-Lara, V.; Urrutia, J., Vertex critical r-dichromatic tournaments, Discrete math., 49, 83-87, (1984) · Zbl 0532.05031
[10] 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
[11] 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.