zbMATH — the first resource for mathematics

The Hoàng-Reed conjecture for \(\delta ^{+}=3\). (English) Zbl 1222.05091
Summary: The Hoàng-Reed Conjecture states that a digraph with minimum out-degree \(d\) contains \(d\) dicycles \(C_{1},C_{2},\dots ,C_d\) such that \(C_k\) intersects \(\bigcup _{i<k}C_i\) on at most one vertex, for each \(k\). It was made as a more structural approach to the Caccetta-Häggkvist Conjecture. We introduce the concept of a nearest separator and use it to prove a stronger version of the Hoàng-Reed Conjecture for the \(\delta ^{+}=2\) case. With these two tools we go on to prove the \(\delta ^{+}=3\) case.

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2001), Springer-Verlag London Limited · Zbl 0958.05002
[2] Bermond, J.C.; Thomassen, C., Cycles in digraphs—a survey, J. graph theory, 5, 1-43, (1981) · Zbl 0458.05035
[3] Caccetta, L.; Häggkvist, R., On minimal digraphs with given girth, (), 181-187 · Zbl 0406.05033
[4] Hamidoune, Y.O., A note on minimal directed graphs with given girth, J. combin. theory ser. B, 43, 343-348, (1987) · Zbl 0643.05036
[5] Havet, F.; Thomassé, S.; Yeo, A., Hoàng – reed conjecture holds for tournaments, Discrete math., 308, 3412-3415, (2008) · Zbl 1147.05038
[6] Hoàng, C.T.; Reed, B., A note on short cycles in digraphs, Discrete math., 66, 103-107, (1987) · Zbl 0626.05021
[7] B.D. Sullivan, A summary of results and problems related to the Caccetta-Häggkvist conjecture, preprint.
[8] Thomassen, C., Disjoint cycles in digraphs, Combinatorica, 3, 393-396, (1983) · Zbl 0527.05036
[9] Thomassen, C., The 2-linkage problem for acyclic digraphs, Discrete math., 55, 73-87, (1985) · Zbl 0563.05027
[10] Thomassen, C., Even cycles in directed graphs, European J. combin., 6, 85-89, (1985) · Zbl 0606.05039
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.