The acyclic disconnection of a digraph. (English) Zbl 0928.05033

The author introduces a new invariant of digraphs: the acyclic disconnection of a digraph \(D\) is the minimum number of connected components of the subgraphs obtained from \(D\) by deleting an acyclic set of arcs. Some results are obtained about this invariant, in general, and for circulant tournaments, in particular.
Reviewer: G.Gutin (Odense)


05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Alspach, B., Cycles of each length in regular tournaments, Canad. math. bull., 10, 283-285, (1967) · Zbl 0148.43602
[2] Arocha, J.; Bracho, J.; Neumann-Lara, V., On the minimum size of tight hypergraphs, J. graph theory, 16, 4, 319-326, (1992) · Zbl 0776.05079
[3] Bang-Jensen, J.; Gutin, G., Paths, trees and cycles in tournaments, (), 131-170 · Zbl 0894.05032
[4] Bang-Jensen, J.; Gutin, G., Paths and cycles in extended and decomposable digraphs, Discrete math., 164, 5-19, (1997) · Zbl 0872.05028
[5] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Elsevier New York · Zbl 1134.05001
[6] Erdös, P., Problems and results in number theory and graph theory, (), 3-21
[7] Erdös, P.; Gimbel, J.; Kratsch, D., Some extremal results in cochromatic and dichromatic theory, J. graph theory, 15, 6, 579-585, (1991) · Zbl 0743.05047
[8] P. Erdös, V. Neumann-Lara, On the dichromatic number of a graph, in preparation.
[9] Jacob, H.; Meyniel, H., Extension of Turan’s and brooks’ theorems and new notions of stability and coloring in digraphs, Ann. discrete math., 17, 365-370, (1983) · Zbl 0525.05027
[10] Neumann-Lara, V., The dichromatic number of a digraph, J. combin. theory ser. B, 33, 265-270, (1982) · Zbl 0506.05031
[11] Neumann-Lara, V., The generalized dichromatic number of a digraph, Colloquia math. soc. János bolyai, 37, 601-606, (1981)
[12] Neumann-Lara, V., The 3 and 4-dichromatic tournaments of minimum order, Discrete math., 135, 233-243, (1994) · Zbl 0829.05028
[13] Neumann-Lara, V., Vertex critical 4-dichromatic circulant tournaments, Discrete math., 170, 289-291, (1997) · Zbl 0876.05039
[14] V. Neumann-Lara, M.A. Pizaña, Externally loose k-dichromatic tournaments, in preparation.
[15] Neumann-Lara, V.; Urrutia, J., Vertex critical r-dichromatic tournaments, Discrete math., 40, 83-87, (1984) · Zbl 0532.05031
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.